(파이썬) 백준 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)가 주어진다.

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

구상

분모를 a, 분자를 b라 하자. k는 대각선으로 몇 번 왔다갔다 했는지 나타낸다.

k	a	b	count
1	1	1	1
2	1	2	2
	2	1	3
3	3	1	4
	2	2	5
	1	3	6
...	...	...	...

k가 홀수일 때 a는 k부터 1까지 감소하고, b는 1부터 k까지 증가한다.

k가 짝수일 때 a는 1부터 k까지 증가하고, b는 k부터 1까지 감소한다.

두 가지 경우로 나누어 a와 b를 증가 or 감소시키고, 매 연산마다 count를 증가시킨다.

count가 x와 같아지면 반복을 종료하고, a/b를 출력한다.

코드

import sys

x = int(sys.stdin.readline())
k = 1
count = 0
a = 1
b = 1

while True:
    if count == x:
        break
    if k % 2 == 0:        #짝수일 때
        a = 1
        b = k
        count += 1
        while a != k:
            if count == x:
                break
            a += 1
            b -= 1
            count += 1
    else:        #홀수일 때
        a = k
        b = 1
        count += 1
        while b != k:
            if count == x:
                break
            a -= 1
            b += 1
            count += 1
    k += 1

print(f"{a}/{b}")

처음엔 이렇게 작성했다. 첫 번째 분수부터 x 번째 분수까지 반복하는 코드다. 결과는 잘 나왔지만 백준에선 시간 초과로 오답처리했다.

처음부터 진행하니 수가 커지면 불필요한 반복이 너무 많아진다. 이 과정을 없애야 한다.

위 표를 보면

k = 1일 때 count = 1,

k = 2일 때 count = 3,

k = 3일 때 count = 6까지 증가함을 알 수 있다.

x = 14라 하자. k = 5일 때 count = 14이면 반복을 종료한다. k가 4일 때까지(count가 10일 때까지) 분수를 증가 or 감소시키는 과정은 생략해도 무방하다. 어차피 k가 5로 바뀌는 순간 분모와 분자는 새로운 값이 되기 떄문이다.

따라서

while count < x:
    count += k
    k += 1
k -= 1
count -= k

x = 14이면 k = 5, count = 10부터 반복을 시작할 수 있도록 위 코드를 추가했다.

 

정답 코드:

import sys

x = int(sys.stdin.readline())
count = 0
k = 1
a = 1
b = 1

while count < x:
    count += k
    k += 1
k -= 1
count -= k

if k % 2 == 0:      #짝수일 때 
    a = 1
    b = k
    count += 1
    while a != k:
        if count == x:
            break
        a += 1
        b -= 1
        count += 1
else:               #홀수일 때
    a = k
    b = 1
    count += 1
    while b != k:
        if count == x:
            break
        a -= 1
        b += 1
        count += 1

print(f"{a}/{b}")