링크

9465 스티커

문제

풀이

대충 적은거라 맨 위에 1번 2번 3번만 체크하면 된다. 3가지 경우의 수를 보자
일단 dp에 첫번째 값과 두번째값은 계산하기 편하도록 넣어주자 그리고 n이 1부터니까 arr[1][0]과 같은 부분은 인덱스 밖으로 나갈 수 있으니 1일 경우를 체크해줘야 된다.

나는 사진처럼 풀려고 했는데 dp[길이][2]이 부분을 잘못 생각하고 반대로 적었다. 그래서 dp[2][길이]라고 생각하면 되겠다.

	//첫번째 값
	dp[0][0] = arr[0][0];
    dp[1][0] = arr[1][0];

	//두번째 값
	dp[0][1] = arr[0][1] + arr[1][0];
	dp[1][1] = arr[0][0] + arr[1][1];

1번의 경우
바로 왼쪽의 대각선을 더하면 된다.

dp[0][i] = dp[1][i-1] + arr[0][i];
dp[1][i] = dp[0][i-1] + arr[1][i];

2번의 경우
한칸 띄고 대각선

dp[0][i] = dp[1][i-2]+ arr[0][i];
dp[1][i] = dp[0][i-2] + arr[1][i];

3번의 경우
한칸 띄고 같은 줄

dp[0][i] = dp[0][i-2]+ arr[0][i];
dp[1][i] = dp[1][i-2] + arr[1][i];

이 경우의 수 중 가장 큰 값을 dp에 저장해두면 된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int t=0;t<testCase;t++){
            int n = Integer.parseInt(br.readLine());

            int[][] arr = new int[2][n];
            int[][] dp = new int[2][n];

            for(int i=0;i<2;i++){
                String[] arr1 = br.readLine().split(" ");

                for(int j=0;j<arr1.length;j++){
                    arr[i][j] = Integer.parseInt(arr1[j]);
                }
//                System.out.println(Arrays.toString(arr[i]));
            }

//            for(int i=0;i<arr.length;i++){
//                System.out.println(Arrays.toString(arr[i]));
//            }

//            System.out.println("------------------------------");

            if(n >= 2){
                dp[0][0] = arr[0][0];
                dp[1][0] = arr[1][0];

                dp[0][1] = arr[0][1] + arr[1][0];
                dp[1][1] = arr[0][0] + arr[1][1];

                for(int i=2;i<arr[0].length;i++){
                    //첫번째 dp[1 or 0][i-1]은 바로 옆 대각선
                    //두번째 dp[1 or 0][i-2]은 한칸 건너뛰고 대각선 or 같은 줄
//                System.out.println(i);
                    dp[0][i] = Math.max(dp[1][i-1], Math.max(dp[0][i-2], dp[1][i-2])) + arr[0][i];
                    dp[1][i] = Math.max(dp[0][i-1], Math.max(dp[0][i-2], dp[1][i-2])) + arr[1][i];
                }

//            System.out.println(Arrays.toString(dp[0]));
//            System.out.println(Arrays.toString(dp[1]));
            } else{
                dp[0][0] = arr[0][0];
                dp[1][0] = arr[1][0];
            }

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

    }


}