[동적계획법 (D.P.)] 백준 9465: 스티커, Java

1. 접근

단순히 대각선으로, 그리고 순차적으로 오른쪽 방향으로 점점 숫자를 쌓아나가

n 번째 스티커 2장을 비교하여 출력하면 될 줄 알았습니다.

하지만 꼭 대각선으로 나아가야 한다는 규칙은 없었고 그것이 꼭 최댓값을 출력한다는 보장은 없었습니다.

 

2. 해결

그럼 도대체 어떻게 최댓값을 구할 수 있을까 생각하는 도중

현재 스티커에 접해 있는 스티커는 사용할 수 없으니 사용할 수 없는 스티커를 제외한

최대의 수를 가질 스티커를 골라서 비교하면 되는 간단한 문제였습니다.

 

n - 1 번째 대각으로 구해오던 수와

그의 바로 뒤쪽에 있는 n - 2 번째 수를 비교하면 최댓값을 구할 수 있었습니다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[][] arr = new int[2][n + 1];
            int[][] dp = new int[2][n + 1];
            int ans = 0;

            for (int j = 0; j < 2; j++) {
                String[] input = br.readLine().split(" ");
                for (int k = 1; k <= n; k++) {
                    arr[j][k] = Integer.parseInt(input[k - 1]);
                }
            }

            dp[0][1] = arr[0][1];
            dp[1][1] = arr[1][1];

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

            ans = Math.max(dp[0][n], dp[1][n]);

            System.out.println(ans);
        }
    }
}