[백준] 1193번 - 분수찾기

1. 문제

https://www.acmicpc.net/problem/1193

 

2. 코드

n = int(input())
cnt = 1
while 1:
    if n <= cnt:
        break
    n -= cnt
    cnt += 1
    
if cnt%2 == 0:
    print('%d/%d'%(n, cnt-n+1))
else:
    print('%d/%d'%(cnt-n+1, n))

 

 

 

3. 알고리즘

첫번째 대각선은 1. 두번째 대각선은 2~3. 세번째 대각선은 4~6번째가 있다. 각 대각선이 갖고 있는 수의 개수는 1, 2, 3....의 순서대로 늘어난다.

그리고 첫번째 대각선의 분모, 분자의 합은 2, 두번째 대각선의 분모, 분자의 합은 3, 세번째는 4이다.

또한 짝수번째 대각선의 경우 위의 수부터 순서가 내려오고(2번째의 경우 위의 수부터 2번째, 3번째 분수로 아래로 내려갈수록 수는 올라감을 알 수 있다.), 홀수번째 대각선의 경우 아래의 수부터 순서가 올라간다.(3번째 대각선의 경우 위의 수부터 6, 5, 4번째 분수로 아래로 내려갈수록 수도 내려간다.)

따라서, X번째 분수를 구하고자 할 때, X에서 1, 2, 3, ...(cnt) 차례대로 수를 빼준다. 여기서 cnt는 몇번째 대각선인지를 나타낸다. 그리고 더이상 뺄 수 없게 되었을 때, 짝수번재 대각선이라면 n/(cnt-n+1이, 홀수번째 대각선이라면 (cnt-n+1) / n이 해당하는 분수이다.