DP - 점화식의 중요성(BOJ 11052, 16194)

요새 다이나믹 프로그래밍(Dynamic Programming)을 공부 중인데, 한 번 새로운 깨달음을 얻을 때마다 문제가 슝슝 풀리는 게 기분이 좋다. 강의를 들으면서, 종만북에서 얻지 못할 좋은 사고의 흐름을 얻었는데, 같이 공유할까 한다(물론 종만북은 너무 어려워서 아직 제대로 보지도 못했다. 그래서 종만북에도 있을 수 있는 내용이다. 갓갓 종만북).

 

먼저, DP의 구조는 익히 들어서 알 것이다. 겹치는 부분 문제(Overlapping problem)와 최적 부분 구조(Optimal substructure)을 둘 다 만족해야 한다. 구조의 정의는 한글말이니 이해하겠는데, 문제에서 해당 정의를 찾아내는 게 나에겐 너무 어려웠다. 기본 개념을 문제에 적용을 못 시키고 있었달까??

 

그렇게 혼자 헤매다가, 강의에서 점화식을 이용해 문제 풀이를 설명하는 걸 듣게 됐는데, 이게 DP를 푸는 데 있어서 정말 중요한 사고라는 걸 알게 됐다. 설명하자면 DP 문제에서 우리가 구하고자 하는 값을 n번째 값이라고 정의를 한다.

D[n] = 구하고자 하는 n번째 값(ex: n번째 원소를 가지는 최대 부분 순열길이의 합)

이게 무슨 소리인가 싶을 수도 있고, 왜 그렇게 해야하냐라고 물을 수도 있다. 하지만 앞서 DP의 정의에서 최적 부분 구조와 겹치는 부분 문제를 만족해야 한다고 했기 때문에, 우리가 구하고자 하는 값은 어떠한 작은 부분 문제의 답으로부터 비롯된 n번째 값임을 이해할 수 있다.

 

저렇게 정의를 하고 나면, 이제 D[n]을 구성하는 점화식을 작성하면 된다.

Ex) D[n] = arr[n] + D[n - 1]

물론 이 부분이 가장 어려운 부분이다. 제일 작은 부분 구조를 파악하는 능력이 필요하기 때문이다. 하지만 점화식의 값을 정의하고, 이 때 D[n - 1]과의 부분구조를 파악하겠다는 사고의 흐름을 가지고 문제를 푸는 것과 바로 문제에서부터 파악하는 것은 완전히 다르다(물론 내가 못하는 것일 가능성이 크다). 

 

아무튼 앞으로 DP를 만나면 점화식으로 작성할 수 있음을 알고, 점화식을 구하겠다는 마음가짐으로 문제를 접근하면 이전과는 다른 신세계를 맛볼 것이라고 장담할 수 있다.

 

다음은 백준에서 내가 문제를 풀면서 작성한 점화식과 소스코드이다.

 

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

11052번: 카드 구매하기

 

// 4개를 구매하려고 한다...
// 모든 조합의 수를 구한다?
// 1111 211 22 31 4
// 11111 2111 221 311 32 41 5
// 111111 21111 2211 222 3111 321 33 411 42 51 6
// p(n)짜릴 삿다는 건,n * m < N을 만족할 때까지 n개짜리 카드를 사겠다는 의미
// 그렇다면 n개짜리 카드를 산다는 걸 어떻게 알 수 있을까?
// D[n] = n개의 카드를 사는 데 최대 비용
// c[n] = n개짜리 카드팩 구매 비용
// = c[n]
// = D[0] + c[n]
// = D[1] + c[n - 1]
// = D[2] + c[n - 2]
// ...중 최대값 (Math.max)
// D[2] = Math.max(c[2], D[1] + c[1]);

처음 부분을 살펴보면, 완전 탐색으로 접근하는 데, 이는 물론 중요하다. 컴퓨팅의 어마어마한 계산 능력을 이용하는 것이기 때문이다. 하지만, 이 문제의 경우 완전 탐색으로도 가능하지만 그렇게 되면 문제가 복잡하고, 중복되는 게 많게 된다. 그래서 아래 빨간색 주석의 사고로 접근했다.

 

소스코드는 아래에 접어놓았는데, for문을 보면 좋다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int ret = 0;
        int[] D = new int[N + 1];
        String[] cards = ("0 "+ br.readLine()).split(" "); // 0,1,5,6,7

        for(int i = 1; i <= N; i++){
            int max = 0;
            for(int j = i; j > 0 ; j--){
                max = Math.max(max, D[i - j] + Integer.parseInt(cards[j]));
            }
            D[i] = max;
        }
        System.out.println(D[N]);
    
    }

}

 

또 다른 문제르 보자. 이번엔 바로바로 점화식으로 접근했다.

 

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

16194번: 카드 구매하기 2

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int ret = 0;
        int[] D = new int[N + 1];
        String[] cards = ("0 "+ br.readLine()).split(" "); // 0,1,5,6,7

        for(int i = 1; i <= N; i++){
            int min = Integer.parseInt(cards[i]);
            for(int j = 1; j <= i/2 ; j++){
                min = Math.min(min, D[j] + D[i - j]);
            }
            D[i] = min;
        }
        System.out.println(D[N]);

    }

}

 

for문 안에 있는 "min = ..." 부분이 문제를 관통하는 점화식이 된다.  

 

이렇게 DP 문제에 있어, 점화식의 접근의 중요성에 대해 포스팅 해 보았다. 물론 처음엔 이렇게 설명해도 쉽사리 이해가지 않고, 문제에 적응시키기도 어려울 것이다. 하지만 계속 꾸준히 생각하다보면 내가 무슨 말을 했는 지 이해하고, 신세계를 맛볼 것이다.

 

좀 더 어려운 문제는 아래에 남겨둘테니 다들 풀어보면 좋겠다.

 

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

15990번: 1, 2, 3 더하기 5

 

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());
        long[][] D = new long[100001][4];
        D[1][1] = 1;
        D[2][2] = 1;
        D[3][1] = 1;
        D[3][2] = 1;
        D[3][3] = 1;
        for(int i = 4; i <= 100000; i++){
            D[i][1] = (D[i - 1][2] + D[i - 1][3]) % 1000000009;
            D[i][2] = (D[i - 2][1] + D[i - 2][3]) % 1000000009;
            D[i][3] = (D[i - 3][1] + D[i - 3][2]) % 1000000009;
        }
        while(test-- > 0){
            int N = Integer.parseInt(br.readLine());
            // D[n][i] == i로 끝나는 n을 만드는 경우의 수(i = 1,2,3)
            // D[i][0] = D[i][1] + D[i][2] + D[i][3];
            // D[i][1] = D[i - 1][2] + D[i - 1][3] + D[i - 2][1] + D[i - 2][3] + D[i - 3][1] + D[i - 3][2];

            D[N][0] = (D[N][1] + D[N][2] + D[N][3]) % 1000000009;
            System.out.println(D[N][0]);
        }

    }

}