[백준] 9465 스티커

www.acmicpc.net/problem/9465

9465번: 스티커

문제 설명 : 스티커 점수의 최댓값 구하기

문제 풀이 : 

처음에는 대각선끼리만 구한 뒤 마지막의 이전 열부터는 최댓값을 구해서 더하면 되는 줄 알았는데 완전히 틀렸습니다. 

변을 공유하기 때문에 이전 대각선과 현재값을 더한 것과 이전의 전 대각선의 값과 현재값을 더한 것을 비교하여 최댓값을 구하는 방식입니다.

이전의 전 대각선을 구하는 이유는 이전 대각선을 선택하지 않을 때도 있기 때문입니다.

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			int n = sc.nextInt();
			int[][] dp = new int[2][n+1];

			for (int i = 0; i < 2; i++) {
				for (int j = 1; j < n+1; j++) {
					dp[i][j] = sc.nextInt();
				}
			}//end of input
			
			int answer = 0;
            
			// 열이 2일 때 부터 이전의 전 대각선의 값을 구할 수 있음
			for (int i = 2; i < n+1; i++) {
				//이전 대각선, 전전 대각선 비교
				dp[0][i] += Math.max(dp[1][i-2], dp[1][i-1]);
				dp[1][i] += Math.max(dp[0][i-2], dp[0][i-1]);
			}
			System.out.println(Math.max(dp[0][n], dp[1][n]));
			
		}//end of tc
	}
}