1일 1백준 : 1193번 분수찾기

1일 1백준 3일차, 오늘 푼 문제는193번 문제인 "분수찾기"이다.

 

 

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

 

 

 

 

알고리즘 문제 풀이에 대한 경험이 거의 없는 내게는 문제가 처음 준 압도감은 엄청났다.

도대체 이걸 어떻게 풀 수 있지 고민하던 순간 규칙이 보이기 시작했고 순조롭게 해결할 수 있었다.

 

 

나는 특이하게 이 문제에서 배열을 사용했는데, 백준을 통과하는 데에는 배열이 굳이 필요하지 않지만

for문을 통해 여러번 n번째 함수를 찾는 상황에는 배열을 사용하는 것이 좋을 것이라고 판단해 조금 더 앞서가봤다.

 

 

func함수를 보면 num == 1일 때 "1/1"을 출력하게 되어있는데.. 처음엔 "1"을 출력하게 작성해놓고

이걸 한참 동안 알아차리지 못해서 거지같은 "틀렸습니다"를 계속 목격하곤 했다.

분명 알고리즘은 틀림이 없는데도 말이다...

문제가 여기 있었다는 것을 처음 알고 얼마나 억울했던지.....

 

 

 

 

 

 

아래로 내리면 정답 코드가 나옵니다. 문제를 아직 풀지 않으신 분들은 주의해주세요.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.Scanner;

public class pro1193 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] list = new int[4472];
        func1193.getList(list);
        int num = 0;

        num = sc.nextInt();
        func1193.func(list, num);

    }
}


class func1193 {
    public static void getList(int[] list) {
        int num = 0;

        for (int a = 1; a <= list.length; a++) {
            num += a;
            list[a-1] = num;
        }

    }

    public static void func(int[] list, int num) {

        int n, k = 0;

        for (int a = 0; a < list.length; a++) {
            if (num == 1) {
                System.out.println("1/1");
                break;
            } else if (num <= list[a]) {
                n = a + 1;
                k = num - (int) list[a - 1];
                if (n % 2 == 0) {
                    System.out.printf("%d/%d", k, n - k + 1);
                } else {
                    System.out.printf("%d/%d", n - k + 1, k);
                }
                break;
            }

        }
    }
}