문제풀이

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

class Main {
    static public void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            int[][] item = new int[2][N];
            int[][] dp = new int[2][N];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int n = 0; n < N; n++) {
                item[0][n] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int n = 0; n < N; n++) {
                item[1][n] = Integer.parseInt(st.nextToken());
            }

            dp[0][0] = item[0][0];
            dp[1][0] = item[1][0];
            if (N == 1) {
                System.out.println(Math.max(dp[0][0], dp[1][0]));
                continue;
            }

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

            for (int i = 2; i < N; i++) {
                dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + item[0][i];
                dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + item[1][i];
            }

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

저번에 풀었던 스티커 모으기(2)와 비슷한 유형의 문제였다.