문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
| 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 -= kx = 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}")