[백준] 스티커

참고 : www.acmicpc.net/problem/9465

9465번: 스티커

 

 - dp 문제

 

 - 다른 사람 풀이를 찾아보니 조금 다르게 풀어서 기쁘기도 하고 신기하기도 했다.
  (생각을 잘 넓히는 것이 중요한 거 같다)

 - dp[i][0] : i번째 스티커 비용의 최대값 (단 i번째는 반드시 위를 선택)

 - dp[i][1] : i번째 스티커 비용의 최대값 (단 i번째는 반드시 아래를 선택)

 - dp[i][2] : i번째 스티커 비용의 최대값 (단 i번째는 반드시 아무것도 선택하지 않음)

 

 - 해당 식을 바탕으로 dp를 전개 해 나갔다.

 

 -- (다른분 풀이는 아무것도 선택하지 않는 경우가 없고 -1번째와 -2번째의 최대 값이었다.)

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] arr;
        int[][] dp;
        int t = sc.nextInt();
        for(int i = 0; i< t; i++) {
            int n = sc.nextInt();
            arr = new int[100005][2];
            dp = new int[100005][3];
            for(int j = 0; j< n; j++) {
                arr[j][0] = sc.nextInt();
            }
            for(int j = 0; j< n; j++) {
                arr[j][1] = sc.nextInt();
            }
            dp[0][0] = arr[0][0]; // 위 선택
            dp[0][1] = arr[0][1]; // 아래 선택
            dp[0][2] = 0; // 노 선택
            for(int j = 1; j< n; j++) {
                dp[j][0] = Math.max(dp[j-1][1], dp[j-1][2]) + arr[j][0];
                dp[j][1] = Math.max(dp[j-1][2], dp[j-1][0]) + arr[j][1];
                dp[j][2] = Math.max(dp[j-1][0], dp[j-1][1]);
            }
            System.out.println(Math.max(dp[n -1][0], Math.max(dp[n -1][1], dp[n -1][2])));
        }
    }
}