[백준] no1003

문제

N: 입력한 숫자

: 입력한 숫자에서 N-1, N-2에 대한 N-1, N-2를 반복한다.

: 반복하다가 N=0이 나오는 경우와 1이 나오는 경우를 각각 count한다

count값을 순서대로 출력한다

 

문제 링크 : https://www.acmicpc.net/problem/1003

---

원리

: 피보나치

1. 재귀 : 가능 하나, 모든 경우를 전부 확인해야한다

2. DP : 같은 숫자의 경우엔 따로 카운트 하지 않는다(더 빠름)

---

풀이방법

1. 재귀

2. DP

---

나의 코드

1. 재귀 [시간초과]

private static int count0;
private static int count1;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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


    for (int i = 0; i < T; i++) {
        count0 = 0;
        count1 = 0;


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

        recur(N);
        bw.append("" + count0 + " " + count1 + "\n");
    }
    bw.close();
}

private static void recur(int N) {
    if (N == 0) count0++;
    else if (N == 1) count1++;
    else {
        recur(N - 1);
        recur(N - 2);
    }
}

 

2. DP [정석]

static Integer[][] dp = new Integer[41][2];

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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


    for (int i = 0; i < T; i++) {
        dp[0][0] = 1;  // N=0 일 때의 0 호출 횟수
        dp[0][1] = 0;  // N=0 일 때의 1 호출 횟수
        dp[1][0] = 0;  // N=1 일 때의 0 호출 횟수
        dp[1][1] = 1;  // N=1 일 때의 1 호출 횟수

        int N = Integer.parseInt(br.readLine());
        
        Integer[] result =fibonacci(N);
        bw.append(""+result[0] + " " + result[1]+ "\n");
    }
    bw.close();
}

static Integer[] fibonacci(int N) {
    // N에 대한 0, 1의 호출 횟수가 없을 떄(탐색하지 않은 값일 때)
    if(dp[N][0] == null || dp[N][1] == null) {
        // 각 N에 대한 0 호출 횟수와 1 호출 횟수를 재귀호출한다.
        dp[N][0] = fibonacci(N - 1)[0] + fibonacci(N - 2)[0];
        dp[N][1] = fibonacci(N - 1)[1] + fibonacci(N - 2)[1];
    }
    // N에 대한 0과 1, 즉 [N][0]과 [N][1] 을 담고있는 [N]을 반환한다.
    return dp[N];
}

---

레퍼런스 코드

참고 링크 : https://st-lab.tistory.com/124