알고리즘 단계별로 풀어보기 : BOJ-1193(분수찾기)

문제(출처)

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

이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

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

예제 입력

14

예제 출력

2/4

내 풀이

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

public class Main {

    public static void main(String args[]) {

        

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        

        try {

            int num = Integer.parseInt(br.readLine());

            String result = fractionalNumbers(num);

            bw.write(result);

            bw.flush();

            bw.close();

            

        } catch (IOException e) {

            e.printStackTrace();

        }

    }

    

    private static String fractionalNumbers(int num) {

        int molecule = 1;   // 분자

        int denominator = 1;    // 분모

        

        boolean check = true;

        

        String result = "";

        

        if(num ==1) {

            result = molecule +"/"+denominator;

            return result;

        }

//      첫 번째 값이면 바로 반환합니다.

        

        int level = 2;

//      두 번째 값부터 확인합니다.

        int count = 1;

//      첫 번째 값을 세었다는 가정하에 저장합니다.

        

        while(check) {

//          1레벨일 때 1/1

//          2레벨일 때 1/2, 2/1

//          3레벨일 때 3/1, 2/2, 1/3

//          1차,2차로 구분하여 체크합니다.

//          1차는 각 레벨의 첫 번째 인덱스를 셋팅 및 확인합니다.

//          2차는 각 레벨의 두 번째 인덱스부터 i번째까지 셋팅 및 확인합니다.

            

//          1차

            if(level % 2 == 0) {

//              레벨 값이 짝수이면 분모는 i로, 분자는 1로 시작합니다.

                molecule = 1;

                denominator = level;

            }else if(level % 2 != 0) {

//              레벨 값이 홀수이면 분모는 1로, 분자는 i로 시작합니다.

                molecule = level;

                denominator = 1;

            }else {

                

            }

            count++;

            if(num == count) {

                check =false;

                result = molecule +"/"+denominator;

                return result;

            }

            

//          2차

            for(int j = 1; j < level; j++) {

//              첫 번쨰를 제외하고 레벨까지 확인합니다.

                if(level % 2 == 0) {

//                  짝수이면 분모는 -1씩 더하고, 분자는 +1씩 더합니다.

                    molecule += 1;

                    denominator += -1;

                }else if(level % 2 != 0) {

//                  홀수이면 분모는 +1씩 더하고, 분자는 -1씩 더합니다.

                    molecule += -1;

                    denominator += 1;

                }else {

                    

                }

                count++;

                if(num == count) {

                    check =false;

                    result = molecule +"/"+denominator;

                    return result;

                }

            }

            level++;

        }

        return result;

    }

}

내 풀이 해석

1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> 1/4 -> 2/3 -> 3/2 -> 4/1 -> 5/1 -> 4/2 -> 3/3 -> 2/4 -> 1/5

숫자에서 규칙을 찾기 보다 그림을 보고 규칙을 찾는 문제입니다.

그림에서 1/1부터 묶어봅니다.

1/1 -> 1

1/2, 2/1 -> 2

3/1, 2/2, 1/3 -> 3

1/4, 2/3, 3/2, 4/1 -> 4

1에서는 1개, 2에서는 2개, 3에서는 3개, 4에서는 4개~~ 입니다. 

1. 레벨에 따라 포함하고 있는 수가 정해집니다.

2. 레벨이 짝수 일때는 분모 -1, 분자 +1의 값이 규칙적입니다.

3. 레벨이 홀수 일때는 분모 +1, 분자 -1의 값이 규칙적입니다.

4. 레벨이 짝수 일때는 첫 번째 값의 분모가 레벨의 값입니다.

5. 레벨이 홀수 일때는 첫 번째 값의 분자가 레벨의 값입니다.

아쉬운 점

가끔 문제를 이해 하지 못하거나 잘못 이해하는 경우가 있습니다.

코드를 보면 아 헤맷구나 하는게 보입니다.

1. 문제 이해하기

2. 내 생각을 코드에 반영하기

3. 내생각을 컴퓨터를 고려해서 코드에 반영하기

알고리즘 할 때 3번까지 가는게 좋지만 1번부터 헷갈리면 2번까지 힘겹게 끝냅니다.