lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



문제 풀이

이번 문제는 동적계획법 DP의 대표적인 예시인 피보나치 수열을 응응하여 풀 수 있는 문제이다.


아이디어 도출

이번 문제에서는 DP를 통해 피보나치 수열을 도출해내는 동시에 fibo(0)과 fibo(1)의 호출횟수를 각각 구해야 한다. 어떻게 0과 1의 호출횟수를 구할 수 있을까?


간단한 에시를 보자.

1
2
3
4
5

N = 2
fibo(2) = fibo(1) + fibo(0)

N = 3
fibo(3) = (fibo(1) + fibo(0)) + fibo(1)

위 예시처럼 N이 2일 때 0과 1은 각각 1번씩 호출되며, N이 3일 때는 0은 1번, 1은 2번 호출된다. 그렇다면, N에 대하여 0과 1이 호출된 횟수를 함께 저장하면 간단하다.

즉, 한 번 탐색할 때마다 N의 0과 1의 호출횟수를 DP 테이블에 저장한 후, 메모이제이션을 통해 이미 저장해둔 N의 호출횟수를 그대로 반환해주면 된다는 것이다.


이를 통해 생각해낸 아이디어는 다음과 같다.

  1. 0과 1의 호출횟수를 함께 담아야 하기 때문에 DP 테이블을 2차원 배열로 선언한다.
  2. 피보나치 함수(fibo)는 N에 대한 0과 1의 호출회수를 DP 테이블에 저장해가며 재귀함수를 호출한다.

메모이제이션을 통해 이미 N에 대해 0과 1의 호출횟수를 구해두었다면 바로 반환한다.

  1. 재귀함수 호출이 종료되면 해당 N의 대한 0과 1의 호출횟수를 1차원배열의 형태로 반환한다.


문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

import java.io.*;

class Main {    

    // 피보나치 수와 N이 0과 1일 때의 호출횟수도 담아야 하기에 2차원 DP 배열 선언
    static int[][] D;

    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());

        // N의 범위는 최대 40이며, 0 과 1의 호출횟수를 함께 초기화
        D = new int[41][2];
        
        for(int i=0; i<=40; i++) {
            D[i][0] = -1;
            D[i][1] = -1;
        }

        // N이 0일 때는 0의 호출횟수가 1, 1의 호출횟수는 0
        D[0][0] = 1;
        D[0][1] = 0;
        // N이 1일 때, 0의 호출횟수 0, 1의 호출횟수 1
        D[1][0] = 0;
        D[1][1] = 1;

        for(int i=0; i<T; i++) {
            
            int N = Integer.parseInt(br.readLine());   
            
            // 테스트케이스별로 N에 대한 피보나치 재귀함수를 실행한다.
            int[] count = fibo(N);

            // 재귀 호출 이후 N에 대한 0과 1의 호출횟수를 출력한다.
            bw.write(count[0] + " " + count[1] + "\n");
            
        }

        bw.close();
        br.close();
    }    

    static int[] fibo(int N) {

        /**
         * N에 대해 0과 1의 호출횟수를 구하지 않았을 경우 
         * 재귀를 통해 0과 1의 호춣횟수를 저장한다.
         */
        if(D[N][0] == -1 && D[N][1] == -1) {
            D[N][0] = fibo(N-1)[0] + fibo(N-2)[0];
            D[N][1] = fibo(N-1)[1] + fibo(N-2)[1];
        }
        
        // [메모이제이션] N에 대해 이미 0과 1의 호출횟수를 구해뒀을 경우 바로 반환한다.
        return D[N];

    }

}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy