[백준온라인저지/BOJ] 1193번 분수찾기

문제

---

풀이

---

필자의 경우 분수의 규칙을 찾아 문제를 해결했다.

분수표의 규칙

첫 번째로 주목해야 할 부분은 첫 번째 열이다.

첫 번째 열의 인덱스를 나열하면 1, 3, 4, 10, 11 인데, 증가하는 값을 보면

2, 1, 6, 1, 10, 1... 순으로 값이 증가함을 알 수 있다.

2부터 짝수번째 차례엔 이전 짝수번째 증가값에 4를 더한 값이, 홀수번째 차례엔 1씩 증가함을 알 수 있다.

 

첫 번째 열 인덱스의 패턴

두 번째로 주목해야 할 부분은 첫 번째 열 인덱스의 수 증감패턴이다.

1이 증가한 홀수번째 차례 이후에는 인덱스가 대각선으로 1씩 증가하고,

4가 증가한 짝수번째 차례 이후에는 인덱스가 대각선으로 1씩 감소함을 알 수 있다.

ex) 인덱스가 3일 경우, 홀수번째 차례이기 때문에 1 증가.

     인덱스는 4가 되고 대각선으로 1씩 증가하여 4, 5, 6이 된다.

홀수는 1씩 증가, 짝수는 1씩 감소하는 패턴

 

마지막으로 인덱스가 봐야할 부분은 대각선 인덱스 별 분자, 분모이다.

대각선으로 올라갈 수록 분자는 1씩 감소하고, 분모는 1씩 증가함을 알 수 있다.

분자는 1씩 감소, 분모는 1씩 증가

 

일단 인덱스 값을 더할 때마다 그 과정을 카운트하는 변수를 cnt, 입력한 값을 inputNum이라고 가정하자.

 

짝수차례인 경우 인덱스 값에 4를 더하고, 해당 인덱스부터 cnt를 뺀 값까지의 범위(인덱스~(인덱스-cnt)) 속에 inputNum이 있는지 체크한다.

만약 값이 존재한다면, cnt-(인덱스-inputNum)을 분자로, 1+(인덱스-inputNum)을 분모로 넣어준다.

 

홀수차례인 경우 인덱스 값에 1을 더하고, 해당 인덱스부터 cnt를 더한 값까지의 범위(인덱스~(인덱스+cnt)) 속에 inputNum이 있는지 체크한다.

만약 값이 존재한다면, cnt-(inputNum-인덱스)를 분자로, 1+(inputNum-인덱스)를 분모로 넣어준다.

 

cnt 만큼 인덱스 값이 대각선으로 증가, 감소하기 때문이다.

 

 

---

따라서 코드로 구현하면 다음과 같다.

import java.util.Scanner;
public class Main {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int inputNum = scanner.nextInt();
        int tmp = 1;
        int addNum = 2;
        int firstNum = 1;
        int lastNum = 1;

        int i = 0;

        while (true){
            if(inputNum == 1){
                break;
            }

            if(i%2 == 0){
                tmp += addNum;
                addNum += 4;
                firstNum += 1;
                if(tmp-(i+1) <= inputNum && inputNum <= tmp){
                    firstNum = firstNum - (tmp-inputNum);
                    lastNum = lastNum + (tmp-inputNum);
                    break;
                }
            }
            else{
                tmp += 1;
                firstNum += 1;
                if(tmp+(i+1) >= inputNum && inputNum >= tmp){
                    firstNum = firstNum - (inputNum - tmp);
                    lastNum = lastNum + (inputNum - tmp);
                    break;
                }
            }
            i++;
        }
        System.out.println(firstNum + "/" + lastNum);
    }
}