[백준 9465번] 스티커

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

package dp;

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

public class DP9465 {

    static int N;

    static int[][] arr;
    static int[][] dp;

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

        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());

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

            solution();
        }
    }

    private static void solution() {
        dp[0][1] = arr[0][0];
        dp[1][1] = arr[1][0];

        for (int j = 2; j < N + 1; 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];
        }

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

 

전형적인 DP의 문제이다. 

초반에는 경우의 수가 너무 많아서 어떻게 풀어야 될지 감이 안왔다. 하지만 DP 문제니깐 단위를 나누어서 쪼개봐서 생각을 해봤다.  

01	02	03
11	12	13

 

이렇게 있다고 가정하면 02는 11과 합쳐서 dp[0][2]=dp[1][1] + arr[0][2] 를 넣는다. 12는 01과 합쳐서 dp[1][2]=dp[0][1] + arr[1][2] 를 넣는다.  

그럼 03은 dp[1][1] 과 dp[1][2] 중 큰 값을 비교해서 넣어줌과 동시에 arr[1][3]을 더해주면 된다. 13도 마찬가지!! 

이렇게 쭉 계산해서 마지막 최종에서 큰 값을 비교하면된다.