[백준] 1193 (분수찾기)

문제 요약

무한히 큰 2차원 배열에 다음과 같이 분수들이 적혀 있습니다.

1/1	1/2	1/3	1/4
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의 범위는 100만까지입니다.

해설

X번 분수가 D번째 대각선에 있다고 해 봅시다. 두 가지 관찰을 할 수 있습니다:

D번째 대각선에는 D개의 분수가 있습니다. 따라서 D번째 대각선의 마지막 번호는 정확히 $\frac{D(D+1)}{2}$ 가 됩니다.
D의 값을 알고 있다면, D의 홀짝성에 따라 분자/분모의 증가 방향이 달라지므로 X번 분수의 값을 쉽게 알 수 있습니다.

D를 효율적으로 구하는 방법은 여러 가지가 있지만, 여기서는 BOJ 2292번 '벌집' 문제를 푸는 반복문 방식을 선택하겠습니다. D를 1씩 증가시키면서 $\frac{D(D+1)}{2}$ 의 값을 계산해, X가 D번째 대각선의 범위 안에 들어오는 순간을 찾으면 됩니다.

D를 구했다면 $\frac{D(D+1)}{2}-X+1$ 와 $X-\frac{D(D-1)}{2}$ 가 각각 분자와 분모의 값이 됨을 알 수 있는데, 둘 중 어느 것이 분자이고 분모인지는 D의 홀짝성에 따라서 달라집니다.

배울 점

'벌집' 문제와 묻는 내용의 결이 비슷하지만, 홀짝성에 따른 조건 분기라는 요소가 가미되었습니다. 두 문제의 공통점을 파악하면 규칙을 찾아 해결하는 수학 문제에 대한 전반적인 이해도가 높아지리라 생각합니다.