[BOJ 9465] 스티커 (S1)

📍 문제 

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

 

 

📍 문제 풀이 

dp[i][j] 는 dp[0][0] ~ dp[i][j]까지 스티커를 떼었을 때 얻을 수 있는 최대 점수

 

• `dp[0][1]`은 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없다는 조건에 의해 `dp[1][0] + dp[0][1]`의 최대값을 가진다.
• `dp[1][1]`도 같은 조건에 의해 `dp[0][0] + dp[1][1]`의 값을 가진다.

 

`dp[0][2]`의 경우에는 `dp[1][0]`과 `dp[1][1]` 중 더 큰 값을 구해야 한다.

 

더 일반적인 경우를 확인하기 위해서 `dp[0][3]`를 살펴보면

이전자리의 스티커를 떼었을 수도 있고, 떼지 않고 건너뛰었을 수도 있다.  

두가지 경우 중 최대 점수를 갖는 경우를 확인해야 한다.

 

즉, `dp[2]`에서 선택을 안 해도 `dp[1][1]`만으로 `dp[1][2]`의 값보다 큰 경우가 존재할 수 있기 때문에

`dp[1][1]`과 `dp[1][2]`중에 큰 값을 확인해야 한다. 

 

 

이를 일반화하여 점화식으로 나타내면 

dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + stickers[0][i];
dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + stickers[1][i];

 

📍 전체 코드

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

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

		for (int t = 0; t < test_case; t++) {
			int n = Integer.parseInt(br.readLine());
			int[][] stickers = new int[2][n];

			for (int i = 0; i < 2; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					stickers[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			int[][] dp = new int[2][n];
			dp[0][0] = stickers[0][0];
			dp[1][0] = stickers[1][0];

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

			sb.append(Math.max(dp[0][n - 1], dp[1][n - 1])).append("\n");
		}
		System.out.println(sb);
	}
}