[JAVA] 백준 9465 - 스티커

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

9465번: 스티커

 

🤔 문제 접근

완전 탐색으로 풀려다가 실패한 문제이다.

 

스티커를 뗀 부분에서 맵을 벗어나지 않는 한도 안에 상하좌우에 있는 스티커가

같이 떼지는 형식이다. 

이때 다음으로 고를 수 있는 스티커의 위치는 현재 뗀 위치의 행이 0인경우

sticker[1][i+1] or sticker[1][i+2] 이고

현재 뗀 위치의 행이 1인 경우엔

sticker[0][i+1] or sticker[0][i+2] 가 된다.

 

다시 말하면 sticker[1][i] 위치의 최대 값을 결정하는 것은

Math.max(sticker[0][i-1], sticker[0][i-2]) + score[1][i] 이고

 

sticker[0][i] 위치의 최대 값을 결정하는 것은

Math.max(sticker[1][i-1], sticker[1][i-2]) + score[0][i] 인 것이다.

 

이후 0행과 1행의 마지막 위치인 n의 값을 서로 대소 비교를 해줌으로써 점수의 최대 값을 구할 수 있다.

 

결과가 하나가 아니고 테스트케이스 별로 나오기 때문에 StringBuilder 에 담아서 한번에 출력하도록 했다.

🚨CODE

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

public class Main {
	public static void main(String[] args) throws Exception  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int tc = 0; tc<T; tc++) {
			int n = Integer.parseInt(br.readLine());
			int[][] score = new int[2][n+1];
			int[][] dp = new int[2][n+1];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			
			for(int i = 1; i<=n; i++) {
				score[0][i] = Integer.parseInt(st.nextToken());
				score[1][i] = Integer.parseInt(st2.nextToken());
			}
			
			dp[0][1] = score[0][1];
			dp[1][1] = score[1][1];
			
			for(int i = 2; i<=n; i++) {
				dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + score[0][i];
				dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + score[1][i];
			}
			sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");
		}
		System.out.println(sb);
	}
}