문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력
각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

BOJ9465

접근

DP 문제에 약한것같아 집중적으로 풀어보고 있다. 2행으로 이루어진 행렬의 1열부터 시작하여 현재 스티커에 도달할때까지 얻을 수 있는 최대값을 저장해나가는 형식으로 접근했다. 이때, 단순히 바로 직전 열의 다른 행 스티커만 비교하여 지그재그로 나아가는 형식이라고 생각했지만, 필요에 따라 바로 직전 열을 넘기는 경우도 있다는 점이 중요했다. 즉, 0행 i번째 위치의 스티커를 떼는 최대값은, 0행 i-2, 1행 i-1, 1행 i-1, 세 값의 최대값을 모두 고려하여 산정해야한다.

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		int [] result = new int[t];
		for(int i = 0; i < t; i++) {
			int n = sc.nextInt();
			int [][] sticker = new int[2][n];
			for(int j = 0; j < 2; j++) {
				for(int k = 0; k<n; k++) {
					sticker[j][k] = sc.nextInt();
				}
			}
			
			int [][] DP = new int[2][n];
			DP[0][0] = sticker[0][0];
			DP[1][0] = sticker[1][0];
			DP[0][1] = DP[1][0] + sticker[0][1];
			DP[1][1] = DP[0][0] + sticker[1][1];
			for(int a = 2; a < n; a++) {
				DP[0][a] = sticker[0][a] + MAX(DP[0][a-2], DP[1][a-2], DP[1][a-1]);
				DP[1][a] = sticker[1][a] + MAX(DP[1][a-2], DP[0][a-2], DP[0][a-1]);
			}
			
			int tmp = DP[0][n-2];
			int tmp2 = MAX(DP[1][n-2], DP[0][n-1], DP[1][n-1]);
			if(tmp2 > tmp)
				tmp = tmp2;
			result[i] = tmp;
		}
		for(int i = 0; i<t; i++)
			System.out.println(result[i]);
	}

	private static int MAX(int i, int j, int k) {
		int max = i;
		if(j>max)
			max = j;
		if(k>max)
			max = k;
		return max;
	}

}