[JAVA] 백준 9465번 【스티커】

점수표 Sticker 배열 S가 위와 같이 있다고 생각해보자.

그리고 Sticker 배열과 크기가 같은 Dp 배열이 있다고 생각해보자.

Dp 배열은 해당 위치를 뜯었을 때, 얻을 수 있는 최대의 점수를 기록해 나갈 것이다.

먼저 Dp[0][1] 과 Dp[1][1]은 간단하다. 해당하는 부분을 뜯었을 때, 해당하는 점수만 획득할 수 있을 것이다.

그렇다면, 두번째 열부터는 점수가 어떻게 될까?

노란 바탕이 스티커를 뜯은 부분이라고 생각할때,

S[0][2] 를 뜯었을 때 얻을 수 있는 최고 점수는,

상식적으로 하나만 뜯는것이 아닌, 인접하지 않은 S[1][1]까지 뜯은 점수의 합일 것이다.

즉 Dp는

해당 위치를 뜯었을 때 얻을 수 있는 최대 점수를 기록하는 것이기 때문에, 위와 같이 기록할 수 있다.

3번째 열은 어떻게 될까?

S[0][3]의 경우 2가지 방법으로 스티커를 뜯을 수 있다.

Case. 1의 경우 S[0][1] + S[1][2] + S[0][3] 의 점수를 획득할 수 있고

Case. 2의 경우 S[1][1] + S[0][3] 의 점수를 획득할 수 있다.

둘 중 어떤 방법을 선택해야하는지는 당연히 S[0][1] +S[1][2] 과 S[1][1] 중 큰 점수를 가진 Case를 선택해야 한다.

위의 예시의 경우는 S[0][1] +S[1][2] = 100 이고 S[1][1] = 30 이기 때문에, Case.1 이 더 높은 점수를 획득할 수 있지만,

Case. 2 가 더 유리한 경우도 있다.

위의 예시의 경우는, S[0][1] +S[1][2] = 70 이고 S[1][1] = 80 이기 때문에, Case.2 가 높은 점수를 획득할 수 있다.

즉, 일반화를 시켜보면,

Dp[0][3] = max(S[0][1] + S[1][2] , S[1][1] ) + S[0][3] = max(Dp[1][1] , Dp[0][2]) + S[0][3] 임을 알 수 있다.

마찬가지로 Dp[1][3] = max(S[1][1] + S[0][2] , S[0][1] ) + S[1][3] = max(Dp[0][1] , Dp[0][2]) +S[1][3] 가 된다.

이 규칙을 이용해서 Dp 테이블을 채워나가면 된다!

이 점화식을 n을 2로 입력받아도 작동될 수 있게,

위와 같이 첫번째 열에 점수가 0이 들어가게, Sticker 배열과 Dp 배열을 생성하였다.

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

public class Main  {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.valueOf(br.readLine());
		
		
		for(int i=1;i<=T;i++) {
			int n = Integer.valueOf(br.readLine());
			long [][] Sticker = new long[2][n+1];
			long [][] Dp = new long[2][n+1];
			
			//Sticker 와 Dp 배열 생성
			for (int j = 0; j < 2; j++) {
				String[] input = br.readLine().split(" "); // 공백 단위로 끊어 배열이 생성됨
				for (int k = 1; k < n+1; k++) {
						Sticker[j][k]= Long.valueOf(input[k-1]); //Sticker 배열에 데이터 채우기
				}
			}
			
			Dp[0][1] = Sticker[0][1];
			Dp[1][1] = Sticker[1][1];
			//초기값 채워주기
			
			for(int j=2;j<=n;j++) {
				Dp[0][j]= Math.max(Dp[1][j-2],Dp[1][j-1])+Sticker[0][j];
				Dp[1][j]= Math.max(Dp[0][j-2],Dp[0][j-1])+Sticker[1][j];
			}
			//스티커 테이블의 열이 2 이상인 경우에 동작
			
			long result = Math.max(Dp[0][n], Dp[1][n]);
			System.out.println(result);
		}
	}
}

티스토리툴바