[Baekjoon Online Judge] 9465번: 스티커

9465번: 스티커

요구사항

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

 - 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 

입력

 - 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다.

 - 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

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

---

50	10	100	20	40
30	50	70	10	60

각 스티커가 가진 가중치가 위와 같다고 가정한다.

 

1, 1은 50의 값을 가장 크게 가져올 수 있다.

2, 1은 30의 값을 가장 크게 가져올 수 있다.

 

1, 2은 30 + 10인 40이 가장 큰 값으로 가져올 수 있다.

2, 2는 50 + 50으로 100을 가장 큰 값으로 가져올 수 있다.

 

1, 3은 총 3가지의 수를 비교할 수 있다. 1, 1과 1, 2, 그리고 2, 2의 값 까지의 집합 중 가장 큰 값을 자신과 더해주어 집합에 포함시킨다.

 

이것을 dp 테이블에 적용해보았다.

 

50	30 + 10	50 + 100 vs 30 + 100 vs 50 + 50 + 100	...	...
30	50 + 50	50 + 70 vs 30 + 70 vs 30 + 10 + 70	...	...

 

50	40	200	140	250
30	100	120	210	260

 

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

public class Baekjoon9465 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(bufferedReader.readLine()); // 테스트 케이스의 개수 T

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(bufferedReader.readLine()); // n
            int[][] stickers = new int[2][n];
            int[][] dp = new int[2][n];

            String[] input = bufferedReader.readLine().split(" ");
            for (int j = 0; j < n; j++)
                stickers[0][j] = Integer.parseInt(input[j]);

            input = bufferedReader.readLine().split(" ");
            for (int j = 0; j < n; j++)
                stickers[1][j] = Integer.parseInt(input[j]);

            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    dp[0][j] = stickers[0][j];
                    dp[1][j] = stickers[1][j];
                } else if (j == 1) {
                    dp[0][j] = stickers[0][j] + dp[1][j - 1];
                    dp[1][j] = stickers[1][j] + dp[0][j - 1];
                } else {
                    dp[0][j] = Math.max(
                            Math.max(stickers[0][j] + dp[0][j - 2], stickers[0][j] + dp[1][j - 2]),
                            stickers[0][j] + dp[1][j - 1]);
                    dp[1][j] = Math.max(
                            Math.max(stickers[1][j] + dp[0][j - 2], stickers[1][j] + dp[1][j - 2]),
                            stickers[1][j] + dp[0][j - 1]);
                }
            }

            System.out.println(Math.max(dp[0][n - 1], dp[1][n - 1]));
        }
        bufferedReader.close();
    }
}