JAVA [Algorithm] - 백준 1193 분수 찾기

 

📝문제 설명

 

---

📢입출력 예시

 

---

✏️문제 풀이

순서는 이런 방향으로 되어 있다.

여기서 한 번 더 생각하면

 

 

대각선으로 분모와 분자의 합이 홀수이면 아래로 내려가는 방향

분모와 분자의 합이 짝수이면 위로 올라가는 방향이 그려지게 된다.

 

그렇다면 완전 탐색을 사용하여 홀, 짝일 때의 경우의 수에 각 칸마다 반복문을 돌려주고 그 값에 count++를 해준 뒤, 입력 값과 똑같다면 값을 출력해주면 된다.

 

 

빨간색 숫자는 첫 반복문으로 i 값이 되고, 이 i값은 분모와 분자의 합이 홀, 짝인지 판단하는 값이 될 것이다.

주황색 숫자는 i값에 대해 두 번째 반복문으로 j=1부터 i값까지 반복문을 돌려주며, count 값을 증가시킨다.

 

package Baekjoon.Simulation;

import java.util.Scanner;

public class Baek1193 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int count = 1;
        boolean end = false;

        for(int i=1; ; i++){
            if(i%2==0){ //짝수일 때 내려가는 방향, 분자 ↑, 분모 ↓
                for(int j=1; j<=i; j++){
                    if(count == N){
                        System.out.println(j + "/" + (i-j+1));
                        end = true;
                        break;
                    }
                    count++;
                }
            }else{ //홀수일 때 올라가는 방향, 분자 ↑, 분모 ↑
                for(int j=1; j<=i; j++){
                    if(count == N){
                        System.out.println((i-j+1) + "/" + j);
                        end = true;
                        break;
                    }
                    count++;
                }
            }
            // 무한 루프로 돌렸기 때문에 외부 반복문 종료해줘야 된다.
            if(end){
                break;
            }
        }
    }
}

---

💡새로 알게된 점

쉬울 줄 알았는데 너무 어려워서 당황;;

---