[BOJ] 1193번

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

 

Python3

 

우선 구간을 나누자고 생각했고 구간을 나누려고 보니 [1/1], [1/2, 2/1], [1/3, 2/2, 3/1] ..... 이런식으로 1, 2, 3, 4 개로 한 줄에 들어갈 수 있는 수의 개수가 1씩 늘어나는 것을 보았다. 저 값들을 차례로 더해갈 때 X보다 커지는 순간 어느 라인에 속하는지 알 수 있을 것으로 생각했다. 따라서 처음에는 반복문을 통해 1부터 차례로 더해가며 X보다 커질 때를 찾았는데 이 방법은 한 라인에서 몇 번째 수인지 알기도 번거로웠다. 또한 값이 커질 때를 찾게되기 때문에 값이 커지기 전에서 멈추려면 조건문이 또 추가되어 코드가 길어졌다.

 

따라서 다음과 같이  코드를 작성했다. 주어진 X가 라인보다 클 때 X에서 각 라인을 빼가면서 몇번째 라인인지 찾았고, 그렇게 남은 X의 값을 통해 라인에서 몇 번째인지 알 수 있었다. 이때 라인이 짝수일 경우 분자가 오름차순 분모가 내림차순, 홀수일 경우 분자가 내림차순 분모가 오름차순이 된다. 따라서 조건을 통해 두 경우를 나누어 분자, 분모 값을 찾았다.