<Algorithm> 194. 스티커(BJO)

1. 9465번 스티커(BJO)

   사용 알고리즘 :  DP

• 처음에 문제를 볼때는 어렵게 보였는데 이전에 푼 와인 문제와 비슷한 DP의 유형이었다.

• 문제에서 최댓값을 원하면서 몇가지 제약조건을 주면 DP로 접근해 점화식을 세워보면 좋을 것 같다.

문제에 대한 접근&생각

1. 인접한 스티커는 땔 수 없으면서 n번쨰 라인까지 스티커의 합의 최대값을 구해야함 -> DP!
2. 임의의 숫자를 선택 -> 이 숫자로 오는 경우들을 확인 -> 점화식 조건!

내 코드 

import java.util.Scanner;
 
public class Main {
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        while(test-->0) {
            int n = sc.nextInt();
            /************************
             * DP를 이용해 경로에 대한 최대치를
             * 구한다.
             ************************/
            int[][] map = new int[2][n];
            int[][] dp = new int[2][n];
            for(int i = 0; i < 2; i++) {
                for(int j =0; j< n; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            dp[0][0] = map[0][0];
            dp[1][0] = map[1][0];
            if(n==1) {
                System.out.println(Math.max(dp[0][0], dp[1][0]));
                return;
            }
            dp[0][1] = map[0][1] + map[1][0];
            dp[1][1] = map[0][0] + map[1][1];
            
            for(int i = 2; i < n; i++) {
                dp[0][i] = Math.max(dp[1][i-2],Math.max(dp[1][i-1], dp[0][i-2]))+map[0][i]; 
                dp[1][i] = Math.max(dp[0][i-2], Math.max(dp[0][i-1], dp[1][i-2]))+map[1][i];
                // 두경우 모두 길이 1 대각선에서 오는 경우, 길이 2 대각선에서  오는경우, 길이 2 직선으로 오는경우
                // 대한 최댓값을 구하고 누적하면 된다.
            }
            System.out.println(Math.max(dp[0][n-1], dp[1][n-1]));
        }
    }
}