[Python] 백준 BaekJoon 1193

 

1193번: 분수찾기

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은

지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

 

출력

첫째 줄에 분수를 출력한다.

 

 

[20.8.21 1차 풀이 실패]

add, count, Start, End 값을 출력했을 때, 행렬의 범위를 벗어난 이상한 값이 나오고 있다 ..

무엇이 문제일까 ...

X = int(input())

add = 0
count = 0
for i in range(X):
    add = add + (i + 1)
    count = i
    if add >= X:
        break

Start = count
End = Start + 1

if End % 2 == 1:
    Start = End - (add - X)
    End = (add - X) + 1
elif End % 2 == 0:
    End = X - (Start + Start)
    Start = add - X + 1

print(f"{End}/{Start}")

---

[20.8.21 2차 풀이]

1차 풀이에서 입력값의 범위가 작을 때만 생각하고 잘못 풀이한 곳이 있었다 ..

End = X - (Start + Start)

오름차순, 내림차순의 역방향 문제인데 if문과 다른 조건식을 걸어둔게 문제였다

 

[풀이법]

1. 입력값의 행렬, 가로 × 세로 범위를 구하기 위해 반복문을 이용한다

add = 0
count = 0
for i in range(X):
    add = add + (i + 1)
    count = i
    if add >= X:
        break

(글을 적으려고 보니 while을 쓰는게 더 효율적이였을 것이란 생각이 든다)

add : 0부터 1씩 증가하는 i값을 더하는데, 저장한 add를 다시 add + i값으로 반복해서 더해준다

       이때, 위 과정을 통해 add가 입력값 X의 범위안에 왔을 때 몇 번째 행렬인지 구분하기 위해

       count를 만들어서 반복이 1회 진행될 때마다 1씩 증가시켰다

       이후 add 값이 X와 같거나 커지면 break를 통해 반복문을 탈출한다

 

2. 반복의 횟수가 곧 열의 개수, count를 Column에 넣어준다

   Row는 Column + 1값을 넣어준다

   Row는 입력값 X가 1/1로 부터 몇 번째에 떨어져 위치하는지 알 수 있게 해준다

   예) X = 7, Row는 4로 1/1을 1칸으로 4/1까지 4칸 떨어진 행렬의 범위에 속하게 된다

Column = count
Row = Column + 1

 

3. 2번의 과정을 통해 알게된 Row를 기준으로 2로 나누었을 때

   그 나머지가 1이라면 홀수번째 위치한 행렬이 되고

   그 나머지가 0이라면 짝수번째 위치한 행렬이 된다

 

   각 행렬에 맞는 Column과 Row를 계산하게 되는데 기준은 이렇다

if Row % 2 == 1:
    Column = Row - (add - X)
    Row = (add - X) + 1

Column은 내림차순이 되어야 하므로 해당 행렬에서 올 수 있는 최대 X값 10 - 입력값을

Row에서 빼주어 내림차순을 계산

Row는 최대값 10 - 입력값에서 +1을 하여 오름차순으로 계산한다

 

* elif는 if와 반대방향으로 오름차순, 내림차순을 바꾸어 계산

 

코드만으로 이해가 잘 되지 않는다면 아래 그림을 참고하면 좋다

add는 입력값 X가 위치한 행렬내에서 올 수 있는 최대 N번째 위치다(빨간색 칸)

그리고 입력값 X가 위치한 행렬내에서 올 수 있는 최소 N번째가 7번째 칸이 된다

 

만약 입력값 X가 8이라면 Row = 4, Column = 3으로 1/1에서 4번째 위치한 행렬이 된다

4번째 행렬은 7, 8, 9, 10에 해당하는 짝수번째 행렬

elif Row % 2 == 0:
    Row = Row - (add - X)
    Column = (add - X) + 1

Row = 4 - (10 - 8)

Column = (10 - 8) + 1

Row = 2, Column = 3 → 2/3이 되며, 예시의 그림과 동일한 위치를 찾게 된다

 

X = int(input())

add = 0
count = 0
for i in range(X):
    add = add + (i + 1)
    count = i
    if add >= X:
        break

Column = count
Row = Column + 1

if Row % 2 == 1:
    Column = Row - (add - X)
    Row = (add - X) + 1
elif Row % 2 == 0:
    Row = Row - (add - X)
    Column = (add - X) + 1

print(f"{Row}/{Column}")

 

* 풀고보니 브론즈 2단계 문제란다 ... 답을 구하는데 2시간 가량 소모되었다 ...