kingsubin

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

public class boj_9465 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st, st2;
    static int[][] dp;
    static int[][] val;
    static int t;

    public static void main(String[] args) throws IOException {
        t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            st2 = new StringTokenizer(br.readLine());

            val = new int[3][n];
            for (int j = 0; j < n; j++) {
                val[1][j] = Integer.parseInt(st.nextToken());
                val[2][j] = Integer.parseInt(st2.nextToken());
            }

            dp = new int[3][n];
            dp[1][0] = val[1][0]; dp[2][0] = val[2][0];

            for (int j = 1; j < n; j++) {
                dp[0][j] = Math.max(Math.max(dp[0][j-1], dp[1][j-1]), dp[2][j-1]);
                dp[1][j] = Math.max(dp[0][j-1], dp[2][j-1]) + val[1][j];
                dp[2][j] = Math.max(dp[0][j-1], dp[1][j-1]) + val[2][j];
            }

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

    }
}

 

- 스티커의 마지막 부분에 초점 

- 경우의수 아무것도 때지않는 경우 0, 위에칸 1, 아래칸 2

- dp[x][n] :: 길이가 n이고 마지막 n 번째일때 때는 스티커가 x 인 점화식 ( x = 0, 1, 2 )

- dp[x][n] = max( dp[x가 아닌 수][n-1] ) + val[x][n] (x 가 0일때는 포함하지않음)

- 0, 1, 2를 n 번째에서 땟을때의 경우의 수 들 중에 최댓값이 ans