백준알고리즘 #1193 분수찾기 java

백준알고리즘 #1193 분수찾기

무한히 큰 배열에서 X번째 분수는 어떤 분수 인가 찾는 문제.

대각선으로 줄을 하나씩 그어보면 각 줄의 개수가 1,2,3... 으로 증가하는게 보인다.

먼저 이 X가 몇번째 줄에 있는지 알아보기 위해 sum이라는 변수를 만들고, X가 sum보다 작아질때까지 while 문을 돌린다. line이라는 변수는 while 문이 몇번 돌아갔는지 (몇 번째 줄인지) 확인하기 위해 생성.

백준알고리즘 #1193 분수찾기 코드

if (n > 1) 을 넣은 이유는 앞서 했던 벌집처럼 1이라면 무조건 1/1이 나오기때문에 제외하기 위해 넣었다.

while문을 빠져나오면 line이라는 변수에 이 X가 몇번째 줄인지 알려주는 수가 담겨져 있다.

이제 이 줄에서 몇번째 순서에 있는지 확인하기 위해 count라는 변수에 n -(sum-line) 값을 넣는다.

(이때 sum 은 X보다 큰 1~n까지의 합 중에서 가장 작은 수)

다만, 이 배열은 지그재그순서로 움직이기 때문에, 2번째 줄은 아래로, 3번째 줄은 위로, 다시 4번째는 아래로...

즉 짝수 줄이라면 아래로, 홀수 줄이라면 위로 올라가는 순서이다.

때문에 짝수 줄이라면 분자에 count가 들어가고, 분모에 line-count +1 이 들어가고, 홀수 줄이라면 그 반대가 된다.