백준 1193 Java

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

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(1 ≤ X ≤ 10,000,000)가 주어진다.

출력
첫째 줄에 분수를 출력한다.

 

이 문제에는 몇가지 규칙이 있다
규칙 1: (분자 + 분모) - 1 = 현재 분자와 분모가 존재하는 라인의 번째수 이자 현재 라인에 존재하는 칸의 개수이다.
규칙 2: (규칙 1의 값이 홀수일때에)오른쪽 대각선으로 상향 할 때 에는 분자의 값이 줄어들고 분모의 값이 늘어난다 3/1, 2/2, 1/3
규칙 3: (규칙 1의 값이 짝수일때에)왼쪽 대각선으로 하향 할 때 에는 분자의 값이 늘어나고 분모의 값이 줄어든다 1/2, 2/1
 
이 규칙들을 이용하여 문제를 풀이하여보자
x =  5 라는 가정을 두고 문제를 풀이하여 보겠다.

 

1. blocks는 대각선의 칸의 개수이며 1부터 시작한다.
 (칸의 개수는 ((분자 + 분모) - 1) 이다)
     
2. prev_block은 이전 칸들의 누적 합 이다.
  (prev_block += ((분자 + 분모) - 1))
     
3. while문의 조건은 true로 break가 나올때까지 반복된다
 
4. if (x <= blocks + prev_block) 의 조건문에 대한 풀이
 (1) (2,3) (4,5,6) (7,8,9,10) 이라는 x가 해당하는 칸의 범위를 생각해보자...!
 x = 5일때에 x 는 3번째 범위의 안에 있으며 그 범위 안에는 (4,5,6)이 해당된다
 이때에 x에 해당하는 분자와 분모를 찾기 위해서는 4 ~ 6 사이의 숫자를 찾아야 하는데
 (x <= 현재 칸의 개수 + 이전 범위의 칸의 누적 개수)를 하여 x가 속한 x와 같거나 큰 범위를 구하면 되는것이다.
 (이떄에 최소값은 x보다 크거나 같아야하기 때문에 x이며 최대값은 (현재 칸의 개수 + 이전 칸의 누적 개수) 이다)
     
5. if(blocks % 2 == 0)의 조건문에대한 풀이
규칙 2,3 을 본다면 대각선 칸의 개수가 홀수라면 오른쪽 상향대각선
짝수라면 왼쪽 하향 대각선으로 값이 늘고 줄어드는 규칙이 있다.
이때에 (blocks % 2  == 0) = true라면 짝수일때의 값을 구해주고
false라면 홀수 일때의 값을 구해주는 것이다.
     
6. x = 5의 범위는 3번쨰 범위(4,5,6)에 해당하며 홀수이다
분자의 값은 줄어들고 분모의 값은 늘어나는 계산을 해주어야 한다
(blocks - (x - prev_block - 1)) + "/"+ (x - prev_block)
    

※ 홀수일때에 분모구하기(홀수와 짝수는 공식의 위치만 앞뒤로 바꾸면 된다)
분모의 계산법: (x - prev_block) 를 해주면 원하는 분모의 값을 찾을 수 있다.
(내가 찾는 숫자와 이전 범위의 칸의 누적 개수를 빼주는 방법이다.
현재 3번째 범위에 해당하는 숫자들을 보면 4,5,6이 해당되며 이때에
4 - 3 = 1, 5 - 3 = 2, 6 - 3 = 3 분모의 값이 늘어나는걸 알 수 있다.)

 

※ 홀수일때에 분자구하기(홀수와 짝수는 공식의 위치만 앞뒤로 바꾸면 된다)
분자의 계산법 : blocks - (x - prev_block - 1)를 해주면 원하는 분자의 값을 찾을 수 있다.
현재 대각선 칸의 개수 - (입력값 - 이전범위의 칸의 누적합 - 1) 을 해주면 된다.
(현재 3번째 범위에 해당하는 숫자들을 보면 4,5,6이 해당되며 이때에
(3 - (4 - 3 - 1) = 3, 3 - (5 - 3 - 1) = 2, 3 - (6 - 3 - 1) = 1 분자의 값이 줄어드는걸 볼 수 있다)
   

규칙을 찾아내어 공식을 만드는것은 참 어려운것 같다...
이 문제로 꽤나 고민하다 풀리지않아 답을 보고 이해하는 방법을 선택하였고
코드를 보고 이해하는건 쉬운데 이걸 풀어서 설명하려니 꽤나 복잡한것 같다.

 

어떻게 해야 간단하게 코드 리뷰를 할 수 있을지 모르겠다

자세히 설명하고싶은데 그렇기에는 풀이가 길어지고

짧게 설명하자니 뭔가 설명이 부족한거같기도하고 쉽지않은 것 같다.