백준 - 9465번 - 스티커

9465번

import java.io.*;
import java.util.*;

public class Main {
	static Integer[][] dp;
	static Integer[][] cost;

	static int recur(int N, int M) {
		if (cost[N][M] == null) {
			if (N == 2) {
				cost[2][1] = dp[1][0] + dp[2][1];
				cost[2][0] = dp[1][1] + dp[2][0];
			}
			else if (M == 1) {
				cost[N][M] = Math.max(recur(N-2, 0), recur(N-1, 0)) + dp[N][1];
			}
			else if (M == 0){
				cost[N][M] = Math.max(recur(N-2, 1), recur(N-1, 1)) + dp[N][0];
			}
		}
		return cost[N][M];
	}
    
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int num = Integer.parseInt(bf.readLine());

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

			if (recur(N, 0) < recur(N, 1)) {
				System.out.println(recur(N, 1));
			} else {
				System.out.println(recur(N, 0));
			}
		}
	}
}

풀이

1. DP 문제라 인식
2. cost[][]를 선언해서 해당 dp[][]까지 최댓값을 저장한다.
3. 최댓값을 어떻게 구하나
   • 이 포인트가 이 문제의 핵심이라 생각한다.