[백준 1193번] 분수찾기(파이썬)

문제

1/1	1/2	1/3	1/4	1/5	…
2/1	2/2	2/3	2/4	…	…
3/1	3/2	3/3	…	…	…
4/1	4/2	…	…	…	…
5/1	…	…	…	…	…
…	…	…	…	…	…

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

 

입력

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

출력

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

 

예제 입력

입력 1
1

입력 2
2

입력 3
3

입력 4
4

입력 5
5

예제 출력

출력 1
1/1

출력 2
1/2

출력 3
2/1

출력 4
3/1

출력 5
2/2

 

---

 

풀이

이 문제는 지그재그 순서로 차례로 나열된 분수가 있고, 숫자가 주어졌을 때 그 숫자 번째의 분수를 구해야 합니다.
지그재그 순서는 1/1 > 1/2 > 2/1 > 3/1 > 2/2 > 1/3 ... 입니다.

먼저 순서를 보기 쉽게 나눠보면
[1/1] > [1/2 > 2/1] > [3/1 > 2/2 > 1/3] ...
이러한 규칙을 찾을 수 있습니다.

규칙에 따라 보기 쉽게 라인으로 나눠봅니다.
1번 라인 : 1/1
2번 라인 : 1/2, 2/1
3번 라인 : 3/1, 2/2, 1/3
4번 라인 : 1/4, 2/3, 3/2, 4/1
5번 라인 : 5/1, 4/2, 3/3, 2/4, 1/5

또 하나의 규칙으로
짝수 라인에 있을 때는 분자가 1씩 작아지고, 분모는 1씩 커지고
홀수 라인에 있을 때는 분자가 1씩 커지고, 분모는 1씩 작아집니다.

그리고 주어진 수가 몇 번째 라인에 속해 있는지를 찾습니다.
1 > 1번 라인                              1                 = 1     > 1
2,3 > 2번 라인                           1+2             = 3     > 2 ~ 3
4,5,6 > 3번 라인                        1+2+3         = 6     > 4 ~ 6
7,8,9,10 > 4번 라인                   1+2+3+4     = 10   > 7 ~ 10
11,12,13,14,16 > 5번 라인        1+2+3+4+5 = 15   > 11 ~ 15

그리고 그 라인에 속해 있는 끝 번째 숫자와 주어진 수의 차(K)를 구하면
1번 라인 : 1/1                                      1/1 > 1번째
2번 라인 : 1/2, 2/1                               2/1 > 3번째
3번 라인 : 3/1, 2/2, 1/3                        1/3 > 6번째
4번 라인 : 1/4, 2/3, 3/2, 4/1                 4/1 > 10번째
5번 라인 : 5/1, 4/2, 3/3, 2/4, 1/5          1/5 > 15번째

                                     ↓  주어진 수에 따라 끝 번째 숫자와 차(K)를 구하면(파란색)

1번 라인 : 1/1                                      1/1 > 1번째
          K =   0
2번 라인 : 1/2, 2/1                               2/1 > 3번째
          K =   1    0
3번 라인 : 3/1, 2/2, 1/3                        1/3 > 6번째
          K =   2     1     0
4번 라인 : 1/4, 2/3, 3/2, 4/1                 4/1 > 10번째
          K =   3     2     1    0
5번 라인 : 5/1, 4/2, 3/3, 2/4, 1/5          1/5 > 15번째
          K =   4     3     2    1     0

이렇게 K를 이용해서 주어진 숫자 번째의 분수를 구할 수 있습니다.

만약 숫자가 13이 주어지면 13번째의 분수는
5번 라인에 있고, K는 15 - 13 = 2 입니다.
5번 라인 홀수 > 분자 1씩 증가, 분모 1씩 감소
분자는 K(2) + 1 = 3
분모는 라인(5) - K(2) = 3 
정답 : 3/3

숫자가 9가 주어지면 9번째의 분수는
4번 라인에 있고, K는 10 - 9 = 1
4번 라인 짝수 > 분자 1씩 감소, 분모 1씩 증가
분자 : 라인(4) - K(1) = 3
분모 : K(1) + 1 = 2
정답 : 3/2

코드를 순서대로 작성한다면
1. 라인, 라인에 속해 있는 끝 번째 숫자를 저장할 변수 선언
2. 주어진 수가 몇번째 라인에 속해 있는지 확인
3. 끝 번째 숫자와 주어진 수의 차의 변수 선언
4. 짝이면 분자 1씩 감소, 분모 1씩 증가, 홀이면 반대
5. 분자, 분모를 출력

---

작성 코드

N = int(input())

line = 0
line_end_num = 0

while line_end_num < N: # 주어진 수가 몇 번째 라인에 속해있는지 확인
    line += 1
    line_end_num += line

K = line_end_num - N # 끝번째 수와 주어진 수의 차

if line % 2 == 0: # 짝수 라인일 때
    a = line - K
    b = K + 1
else:
    a = K + 1
    b = line - K

print(str(a) + '/' + str(b)) # 정수 형태인 a, b를 문자열로 바꾸어 출력