[BOJ] 백준 [9465] 스티커 JAVA

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

9465번: 스티커

문제

풀이

만약 스티커를 하나 떼어 냈다고 가정하면 다음에 뗄 수 있는 스티커는 한칸대각선 or 두칸 대각선이다.
즉 , 이 둘중에 큰 값을 선택하면 끝
반대로 말하면 이전의 스티커 점수의 합은 그림과 같이 둘 중 큰 곳에서 가져오면 된다.
파란색의 스티커를 떼어냈다고 가정을 하면 이전의 점수합은 빨간색 둘 중 큰 값을 가져오면 된다는것.

따라서 점화식은 

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while(tc-->0){
            int n = Integer.parseInt(br.readLine());
            int[][] arr = new int[2][n+2];
            int[][] dp = new int[2][n+2];
            for(int i=0;i<2;i++){
                int[] input = Arrays.stream(br.readLine().split(" ")).
                        mapToInt(Integer::parseInt).toArray();
                for(int j=1;j<=input.length;j++)
                    arr[i][j] = input[j-1];
            }
 
            dp[0][1] = arr[0][1]; dp[1][1] = arr[1][1];
            dp[0][2] = dp[1][1]+arr[0][2];
            dp[1][2] = dp[0][1]+arr[1][2];
 
            for(int i=3;i<=n;i++){
                dp[0][i] = arr[0][i] + Math.max(dp[1][i-1],dp[1][i-2]);
                dp[1][i] = arr[1][i] + Math.max(dp[0][i-1],dp[0][i-2]);
            }
 
            System.out.println(Math.max(dp[0][n],dp[1][n]));
        }
    }
}