[백준] 9465 스티커 [java]

문제

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

풀이

지그재그로 선택하면 칸을 많이 선택할 수 있으니, 두 경우중 하나를 선택하면 되나.. 했는데, 그렇게 간단할 리가 없고,,,

이런 경우도 있다. 이렇게 하면 겹치는거 없이 모든 스티커를 뗄 수 있다.
따라서, 첫번째 경우와 두번째 경우를 모두 고려해야 한다.
그리고, 해당 위치에서 잘 고려해서 최선을 선택하면, 그 이후의 선택도 최선이 될 수 있다 -> dp

100을 탐색할 때, 노란색의 경우와 빨간색의 경우가 있다.

arr[0][2] += Math.max(arr[1][1], arr[1][0]);

이 된다.
따라서 점화식은

arr[0][i] += Math.max(arr[1][i - 1], arr[1][i - 2]);
arr[1][i] += Math.max(arr[0][i - 1], arr[0][i - 2]);

이 된다.

코드

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

// 최대가 되게 스티커 떼기
public class Boj9465 {
//public class Main {
    public static int solution(int[][] arr){
        if(arr[0].length > 1){
            arr[0][1] += arr[1][0];
            arr[1][1] += arr[0][0];
        }

        for(int i = 2; i < arr[0].length; i++){     //열
            arr[0][i] += Math.max(arr[1][i - 1], arr[1][i - 2]);
            arr[1][i] += Math.max(arr[0][i - 1], arr[0][i - 2]);
        }

        return Math.max(arr[0][arr[0].length - 1], arr[1][arr[0].length - 1]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tCase = Integer.parseInt(bufferedReader.readLine());

        while(tCase-- > 0){
            int col = Integer.parseInt(bufferedReader.readLine());
            int[][] arr = new int[2][col];

            for(int i = 0; i < 2; i++){
                StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                for(int j = 0; j < col; j++){
                    arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                }
            }

            System.out.println(solution(arr));
        }
    }
}