[Java] 백준 9465 스티커 / DP 쉬운 예제

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	public static void main(String[] args) throws NumberFormatException, IOException {
		 int T = Integer.parseInt(br.readLine()); //입력되는 테스트케이스 개수
		 for (int i = 0; i < T; i++) {
			 int n = Integer.parseInt(br.readLine());
			 int[][] map = new int[2][n+1];
			 for (int j = 0; j < 2; j++) {
				st = new StringTokenizer(br.readLine());
				for (int k = 1; k <= n; k++) { //맨 앞칸을 띄우고 입력받음(이유는 뒤에)
					map[j][k] = Integer.parseInt(st.nextToken());
				}
			}
			 int[][] dp = new int[2][n+1];
			 dp[0][1] = map[0][1]; //첫칸을 구성하는 최대의 합은 자기자신
			 dp[1][1] = map[1][1];
			 for (int j = 2; j <= n; j++) {
				dp[0][j] = map[0][j]+Math.max(dp[1][j-1],dp[1][j-2]); //다음 칸에 도달 할 수 있는 방법은 대각선 or 대각선 이전칸 뿐
				dp[1][j] = map[1][j]+Math.max(dp[0][j-1],dp[0][j-2]); //이 과정에서 두번째 dp칸 예외를 허용해주기 위해 map 입력을 첫 칸 띄우고 받음
			}
			 System.out.println(Math.max(dp[0][n], dp[1][n]));
		}
	}
}

 

1. dp를 푸는 요령은 각 단계를 구성하는 최소 단계를 찾는 것임

2. 어떠한 방법으로도 합쳐질 수 없는 최소 단위를 반복해 누적하면서 불필요한 단계를 줄이고 빠르게 답에 도달한다

 

 

9465번: 스티커