[알고리즘] 백준 9465 스티커

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

9465번: 스티커

 

import java.util.Scanner;

public class BJ_9465 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();

        for (int k = 0; k < t; k++) {
            int n = scan.nextInt();
            int[][] test = new int[2][n + 1];
            int[][] dp = new int[n + 1][3];

            for (int i = 1; i < n + 1; i++) {
                test[0][i] = scan.nextInt();
            }

            for (int i = 1; i < n + 1; i++) {
                test[1][i] = scan.nextInt();
            }

            dp[1][0] = 0;
            dp[1][1] = test[0][1];
            dp[1][2] = test[1][1];

            for (int i = 2; i < n + 1; i++) {
                dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][2]));
                dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][2]) + test[0][i];
                dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][1]) + test[1][i];
            }

            System.out.println(Math.max(dp[n][0], Math.max(dp[n][1], dp[n][2])));
        }
    }
}

knapsack과 유사한 dp 문제이다.

 

2차원 배열인 test와 dp를 통해 문제를 풀었다.

 

가장 좌측 위아래 스티커부터 순차적으로 선택한다는 가정 하에 문제를 풀었다.

 

스티커를 선택하는 경우의 수는

 

1. 아무것도 고르지 않을 경우(바로 오른쪽 스티커보다 더 오른쪽에 있는 스티커를 고르는 것이 기대값이 큰 경우)

 

2. 위에 스티커를 고르는 경우

 

3. 아래 스티커를 고르는 경우

 

총 세가지로 볼 수 있다. 

 

1번 경우는 dp[i][0]에, 2번 경우는 dp[i][1]에, 3번 경우는 dp[i][2]에 들어가도록 하였다.

 

이를 통하여 규칙을 구할 수 있었는데

 

아무것도 선택하지 않을 경우에는 dp[i - 1][0], dp[i - 1][1], dp[i - 1][2] 중에서 최대값,

 

위에 스티커를 고르는 경우에는 dp[i - 1][0], dp[i - 1][2]의 최대값 + 위에 스티커의 값 (스티커와 닿아있는 부분은 선택할 수 없기에 dp[i - 1][0]과 dp[i - 1][2]를 비교해야 한다.)

 

아래 스티커를 고르는 경우에는 dp[i - 1][0], dp[i - 1][1]의 최대값 + 아래 스티커의 값

 

위의 규칙을 통해 다이나믹 프로그래밍 기법으로 정답을 구할 수 있었다.