[Java] 백준 9465 : 스티커

 

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

9465번: 스티커

---

card []에 가격을 넣어준다. 

0번째 카드가 0 인 것은 나중에 최댓값 찾을 때를 위해 비워 둔 것이다. 

0	50	10	100	20	40
0	30	50	70	10	60

이때 dp[][]에 각 해당하는 자리의 스티커를 떼어냈을 때의 최댓값을 더해 대입하면 된다. 

해당 자리의 윗칸 스티커를 떼려면 직전에 아래칸 스티커를 떼었거나, 직전 아래칸 스티커는 떼지 않고 전전  아래칸 스티커를 떼었거나 할 수 있다. 아래칸 스티커도 마찬가지이다. 

 

이걸 점화식으로 나타내면 

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

이렇게 나타낼 수 있다. 

 

 

---

 

import java.util.*;

public class Main {
	
	public static void main(String[] args){
		Scanner sc= new Scanner(System.in);
		int N=sc.nextInt();
		
		for(int n=0;n<N;n++) {
			int M=sc.nextInt();
			int[][] dp= new int[2][M+1];
			int[][] card= new int[2][M+1];
			
			for(int j=0;j<2;j++) {
				for(int k =1 ;k<=M;k++) {
					card[j][k]=sc.nextInt();
				}
			}
			
			dp[0][1] = card[0][1];
			dp[1][1] = card[1][1];
			
			for (int j = 2; j <= M; j++) {
				dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + card[0][j];
	            dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + card[1][j];
	            }
			
			System.out.println(Math.max(dp[0][M], dp[1][M]));
		}
		
	}// main()
	
}// class Main