[백준 알고리즘]1193번 "분수찾기"

[백준 알고리즘]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)가 주어진다.

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

예제 입력1
1

예제 출력1
1/1

문제 풀이

이 문제는 군수열 문제이다.
{1/1}, {1/2, 2/1}, {3/1, 2/2, 1/3}, {1/4, 2/3, 3/2, 4/1}, ...
묶음 속 분수의 개수는 차례대로 1, 2, 3, 4 로 1씩 커지며 증가한다.

위의 정보를 가지고 문제를 풀어보면

1. 입력받은 X가 몇 번째 묶음에 속해 있는지 찾는다.

2. 찾은 N번째 묶음의 첫 번째 숫자가 무엇인지 찾는다.

3. 그리고 X가 해당 묶음에서 몇 번째 다음에 있는지 찾는다.

4. N이 짝수면, 배열에서 위에서 대각선 방향으로 아래로 내려간다. (분모는 감소하고, 분자는 증가한다)
   N이 홀수면, 배열에서 아래에서 대각선 방향으로 위로 올라간다. (분모는 증가하고, 분자는 감소한다)

5. 해당 분수를 계산하여 출력한다.

x = int(input())
num = 0
variable_add = 1
n = 0
while num < x:
    num += variable_add
    n += 1
    variable_add += 1

first_index = num-(variable_add-1)+1
N_th = x - first_index
if n % 2 == 0:
    a = 1 + N_th
    b = n - N_th
else:
    a = n - N_th
    b = 1 + N_th

print('%d/%d'%(a,b))