> 분수찾기 > Silver V > #[[수학]] #[[구현]] ### 문제 요약 무한히 큰 2차원 배열에 다음과 같이 분수들이 적혀 있습니다. | 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의 범위는 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의 홀짝성에 따라서 달라집니다. ### 배울 점 '벌집' 문제와 묻는 내용의 결이 비슷하지만, 홀짝성에 따른 조건 분기라는 요소가 가미되었습니다. 두 문제의 공통점을 파악하면 규칙을 찾아 해결하는 수학 문제에 대한 전반적인 이해도가 높아지리라 생각합니다.