백준 1193 : 분수찾기

 

---

풀이 방법

백준 브론즈의 탈을 쓴 실버 문제...매번 느끼는 것이지만 백준에서 '수학' 이 붙은 애들은 모두 실버 이상의 난이도라고 생각이된다ㅠㅠ

특히나 규칙을 못 찾으면 차라리 BFS, DFS 문제 푸는게 더 쉽다고 느껴질 정도이다. 이 문제가 특히 그랬는데 뭔가 보일듯 말듯 하면서 시간이 정말 오래걸려서 풀었다.

 

사실 수학 관련 문제가 그렇듯, 이 문제도 점화식을 세우면 혹은 그에 준하는 규칙을 찾으면 해결의 실마리가 보이는 편이다. 짝수 층과 홀수 층에 관한 규칙, n번째 층에 총 몇개의 분수가 오는지 규칙을 찾아서 점화식을 세워야 한다.

 

나는 문제의 지그재그 순 이라는 것을 하나의 층으로 생각하였다. 즉 1층에는 1/1, 2층에는 1/2, 2/1 ---- 이런 식이다.

여기에 각 층에 몇개의 분수가 오는지, 홀수층과 짝수층의 규칙 차이를 찾아서 아래와 같이 정리하였다.

* 1층  1/1
* 2층  1/2 2/1 => 3개
* n번째  2   3
* 3층  3/1 2/2 1/3 => 6개
* n번째  4   5   6
* 4층   1/4 2/3 3/2 4/1 => 10개
* n번째  7    8   9   10
* 5층    5/1 4/2 3/3 2/4 1/5 => 15개
* n번째   11   12   13  14  15
*
* i 층 의 마지막 번호 => 이전층 갯수 + 현재층수(i)
* i가 홀수라면 : i/1 i-1/1+1 i-2/1+2 i-3/1+3  ------ 1/m => 현재 층수만큼 반복
* i가 짝수라면 : 1/i 1+1/i-1 1+2/i-2 1+3/i-3 ------ m/1 => 현재 층수만큼 반복

 

그래서 최종적으로 i 층의 마지막 번호에 대한 점화식을 얻어냈고, 이를 통해서 n 이 몇번째 층에 속하는지 확인한 후 짝수와 홀수에 따라서 코드를 짜 주었다.

 

이 문제는 긴 설명보다는 주석과 문제를 보면서 규칙을 찾으신 후 코드를 짜시면 훨씬 좋을 것이라고 생각합니다!

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// https://www.acmicpc.net/problem/1193
public class Quiz_1193 {
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] lvl = new int[n+1];
        lvl[1] = 1;

        /*
        * 1층  1/1
        * 2층  1/2 2/1 => 3개
        * n번째  2   3
        * 3층  3/1 2/2 1/3 => 6개
        * n번째  4   5   6
        * 4층   1/4 2/3 3/2 4/1 => 10개
        * n번째  7    8   9   10
        * 5층    5/1 4/2 3/3 2/4 1/5 => 15개
        * n번째   11   12   13  14  15
        *
        * i 층 의 마지막 번호 => 이전층 갯수 + 현재층수(i)
        * i가 홀수라면 : i/1 i-1/1+1 i-2/1+2 i-3/1+3  ------ 1/m => 현재 층수만큼 반복
        * i가 짝수라면 : 1/i 1+1/i-1 1+2/i-2 1+3/i-3 ------ m/1 => 현재 층수만큼 반복
         * */
        if(n==1) System.out.println("1/1");

        for(int i=2; i<=n; i++){
            // i 층의 마지막 번호 확인
            // n 이 lvl[i] 보다 작다면 n 은 i 번째 층에 포함된다는 것을 알 수 있다.
            lvl[i] = lvl[i-1]+i;

            // n 이 몇번째 층에 속하는지 확인
            if (n <= lvl[i]) {
                // i 가 짝수면 1/i 에서 시작
                // i 가 홀수면 i/1 에서 시작
                int a = i;
                int b = 1;
//                System.out.println("i : "+i);

                // n번째 값은 현재 층 처음 시작값에서 몇번째 위치에 있는지
                int m = n-(lvl[i-1]+1);


                if ((i) % 2 == 0) {
                    System.out.println((b + m) + "/" + (a - m));
                    break;
                }else{
                    System.out.println((a - m) + "/" + (b + m));
                    break;
                }


            }
        }



    }
}