[Python] BOJ / 1193번 / 분수찾기

1193번: 분수찾기

 

📝 문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

 

📜 풀이

• 대각선 방향으로 라인을 나누어보면 각 라인에 속하는 분수들은 다음과 같이 나눌 수 있다.
  • 1번째 라인: (1/1)
  • 2번째 라인: (1/2), (2/1)
  • 3번째 라인: (3/1), (2/2), (1/3)
  • 4번째 라인: (1/4), (2/3), (3/2), (4/1)
  • ...
• 이때, 홀수번째 라인의 경우 분자는 1씩 늘어나고 분모는 1씩 감소하는 것을 확인할 수 있고, 짝수번째 라인의 경우 분자는 1씩 감소하고 분모는 1씩 늘어나는 것을 확인할 수 있다.
• 위 규칙을 찾았다면, X가 주어졌을 때 X가 몇 번째 라인의 몇 번째 순서에 위치하는지를 알아낸다면 그에 해당하는 분수 역시 알아낼 수 있다.
• X가 속하는 라인의 경우, X와 그 라인의 끝 값과 비교해가면서 X가 끝 값보다 커지는 시점의 바로 직전 라인임을 알 수 있다.
• 또한 X가 해당 라인의 몇 번째 순서에 있는지는 해당 라인의 끝 값과의 거리를 계산하면 알 수 있다.
• 각 라인에 속하는 분수의 갯수는 1 -> 2 -> 3-> 4...의 순으로 증가하며, 이를 통해 각 라인의 끝 값은 1 -> 3(1 + 2) -> 6(3 + 3) -> 10(6 + 4)...의 순으로 증가함을 알 수 있다.

1   2   6   7  ..
3   5   8   ..  ..
4   9   ..   ..  ..
10 ..   ..   ..  ..

..   ..   ..   ..  ..

 

💻 소스코드

x = int(input())

# line: X가 속하는 라인, end: X가 속하는 라인의 끝 값
line = end = 1
while x > end:
    line += 1
    end += line

# X가 속하는 라인에서 X의 위치 = 라인의 끝 값과 X 사이의 거리
diff = end - x

# 분자, 분모
top = bottom = 0

# 짝수번째 라인인 경우
if line % 2 == 0:
    top = line - diff
    bottom = diff + 1

# 홀수번째 라인인 경우
else:
    top = diff + 1
    bottom = line - diff

print(f'{top}/{bottom}')