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

https://www.acmicpc.net/problem/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. 짝수 line: 분모 += 1 / 분자 -= 1

2. 홀수 line: 분모 -= 1 / 분자 += 1

지그재그 순으로 나열한 표를 자세히 보면, 홀수 라인인 1, 3, 5 번째 줄의 분수들은 분모가 1씩 늘어나고 분자가 1씩 줄어든다. 짝수 라인은 그 반대이다.

 

line = 1

while x > line:
    x -= line
    line += 1

해당 while 문을 거치면 x번째의 분수가 몇 번째 줄의 몇 칸에 있는지 알 수 있다.

예를 들어 10번째 분수의 위치를 찾는다고 가정해보자.

 

x	line
10	1
9	2
7	3
4	4

while문을 돌았을 때 업데이트되는 변수 값이다.

여기서 4번째 라인의 4번째 칸에 10번째 분수가 위치하는 걸 알 수 있다.

 

# 짝수인 경우 - 분자 = 칸
if line % 2 == 0:
    a = x
    b = line - x + 1 # ?

# 홀수인 경우 - 분모 = 칸
elif line % 2 == 1:
    a = line - x + 1
    b = x

짝수 라인은 분자가 칸 수에 따라 증가하는 경향이 있어 분자에 x 값을 그대로 세팅해 주면 되고,

홀수 라인은 마찬가지로 분모에 x 값을 세팅해 주면 된다.

 

line - x + 1 <- 이 식이 왜 나왔는지 오랜 시간 고민했는데,, 그냥 수학적 규칙에 따라 나오는 식이었다.

실제로 손으로 풀어보니 해당 식의 규칙대로 분모/분자의 값이 세팅되어 있었다.

 

코드 전문

x = int(input())
line = 1 # 지그재그 순으로 정렬한 배열의 라인 수

# 몇 번째 라인의 몇 번째 칸에 있는지 탐색
# line: 라인 수 / x = 칸
while x > line:
    x -= line
    line += 1

# 짝수인 경우 - 분자 = 칸
if line % 2 == 0:
    a = x
    b = line - x + 1 # ?

# 홀수인 경우 - 분모 = 칸
elif line % 2 == 1:
    a = line - x + 1
    b = x

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