[백준] 스티커 9465 - JAVA

문제

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

9465번: 스티커

 

풀이

다이나믹 프로그래밍으로 풀었다. (내 힘으로 풀었다 드디어 발전하는듯)

DP 배열은 특정 부분의 스티커를 때었을때의 누적 최대값을 나타나도록 만들었다.

예를 들자면, 현재 색칠한 부분의 스티커를 뗀다고 해보자. 이부분의 위치는 (1,2)가 될것이다.

DP 배열

노란색 부분의 dp 값은 다음 두가지가 될 수있다.

1. 왼쪽 대각선 방향의 dp 값 + 현재 스티커 값 (노란색 스티커를 뗄수 있을때)

2. 왼쪽의 DP 값 (노란색 스티커를 뗄수 없을때)

 

1번에 대해 먼저 살펴보자.

스티커를 떼는 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 따라서, 대각선에 있는 스티커만 뗄 수 있게 된다. 그러므로, 노란색 스티커를 떼면 왼쪽 대각선 방향의 스티커는 남게된다. 그러므로, 왼쪽 대각선 방향의 스티커의 최대값, 즉 dp값과 현재 스티커의 값을 더하는 경우가 1번이다.

 

2번은 스티커를 뗄 수 없을때인데 말그대로 다른 스티커가 떼질 때 같이 뜨겨나간 스티커이다. 그 경우는 왼쪽 스티커가 떼졌다는 뜻이므로 왼쪽 스티커의 값이 dp가 될 수 있다.

 

DP 배열을 특정 부분의 스티커를 때었을때의 누적 최대값으로 설정하였다. 그러므로 1과 2번에 대해 max값을 구하면 그것이 특정부분의 dp값이 된다.

 

코드

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

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		for(int task = 0; task < t; task++) {
			int n = Integer.parseInt(br.readLine());
			
			int arr [][] = new int [3][n+1];
			int dp [][] = new int [3][n+1];
			
			for(int i=1;i<=2;i++){
				st = new StringTokenizer(br.readLine());
		
				for(int j=1;j<=n;j++){
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			dp[1][1] = arr[1][1];
			dp[2][1] = arr[2][1];
			
			for(int i = 2; i <= n; i++) {
				dp[1][i] = Math.max(arr[1][i] + dp[2][i-1], dp[1][i-1]);
				dp[2][i] = Math.max(arr[2][i] + dp[1][i-1], dp[2][i-1]);		
			}
			
		
			sb.append(Math.max(dp[1][n], dp[2][n])).append("\n");

		}

		System.out.println(sb);
	}
}