[Algorithm/Java] 다이나믹 프로그래밍 복습

DP문제 해결 과정 = 규칙을 찾아 점화식 세우기

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

처음엔 감이 안잡히므로.. 그냥 몇문제 답을 보고 시작하는게 효율적이다.

💡 ex1. RGB거리

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

1149번: RGB거리

• 주어진 비용으로 N개의 집을 빨, 초, 파로 칠하는데
• N번 집은 N-1, N+1번 집과 색이 같으면 안된다
• 집을 칠하는 최소비용 구하기

1. 점화식 세우기
   • N-1번째 집과 N번째 집의 관계 → 조건은 서로 다른 색
   • 구하는건 최소비용 → min()으로 비교하자
2. 경우의수 생각하기
   • N번째 집이 R, G, B인 경우 3가지

public class BOJ_1149 {

    final static int R = 0;
    final static int G = 1;
    final static int B = 2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] cost = new int[N][3];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            cost[i][R] = Integer.parseInt(st.nextToken());
            cost[i][G] = Integer.parseInt(st.nextToken());
            cost[i][B] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i < N; i++){
            cost[i][0] = cost[i][0] + Math.min(cost[i - 1][1], cost[i - 1][2]);
            cost[i][1] = cost[i][1] + Math.min(cost[i - 1][0], cost[i - 1][2]);
            cost[i][2] = cost[i][2] + Math.min(cost[i - 1][1], cost[i - 1][0]);
        }

        System.out.println(Math.min(Math.min(cost[N-1][R], cost[N-1][G]), cost[N-1][B]));
    }
}

💡 ex2. 정수 삼각형

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

1932번: 정수 삼각형

• 정수 삼각형의 맨 위층에서 시작 → 아래층으로 대각선에 있는 수 하나를 선택하여 내려온다.
• 선택된 수의 합이 최대가 되는 경로 구하기

이 문제도 N층과 N-1층의 관계를 생각하며 점화식을 세우면 된다.

• 각 층의 양 끝에 있는 수 → 바로 위의 수와 그대로 더해진다
• 중간에 있는 수 → 바로 위의 두 수 중 더 큰 수와 더해진다

public class BOJ_1932 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] arr = new int[N][N];
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < i+1; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1; i < N; i++){
            for (int j = 0; j < N; j++){
                if (j == 0){
                    arr[i][j] = arr[i][j] + arr[i - 1][j];
                }
                else if (j == i){
                    arr[i][j] = arr[i][j] + arr[i - 1][j - 1];
                }
                else{
                    arr[i][j] = arr[i][j] + Math.max(arr[i - 1][j - 1], arr[i - 1][j]);
                }
            }
        }
        Arrays.sort(arr[N-1]);
        System.out.println(arr[N-1][N-1]);
    }
}

💡 ex3. 카드 구매하기

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

11052번: 카드 구매하기

• 8가지 등급이 있는 카드는 카드팩의 형태로만 구매할 수 있다.
• 1개, 2개 ,,, N개가 포함된 카드팩 N가지 존재
• 돈을 최대한 많이 지불해서 카드 N개를 구매하려 한다.

N개의 카드 팩이 있고, N개의 카드를 구매하는 상황.

D[i] = 카드 i개를 구매하는 최대 비용, dp[k] = 카드 k개가 들어있는 카드팩의 가격 일 때,

카드 i개를 구매하는 최대 비용의 경우의 수는

D[1] + dp[i - 1]

D[2] + dp[i - 1]

D[3] + dp[i - 3]

...

D[i] + dp[0]

public class BOJ_11052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] D = new int[N+1];
        int[] cost = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= N ; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= i; j++){
                D[i] = Math.max(D[i], cost[j] + D[i - j]);
            }
        }

        System.out.println(D[N]);
    }
}