문제 개요

2행 N열로 배치되어 있는 스티커에 점수가 부여되어 있을 때, 선택 가능한 스티커들의 점수 총합 최대치는 얼마일까를 구하는 문제입니다.

문제 접근

N의 최대 크기가 100,000입니다. 따라서 N2의 시간복잡도를 가질 수 없기 때문에 브루트 포스 방식은 제외해야 합니다.

이 문제는 합계의 최대치를 구하는 문제인데 브루트 포스로 해결할 수 없으므로 그리디 혹은 DP를 생각해볼 수 있습니다.

그래프가 아닌 배열로 주어졌기 때문에 추가적인 구현 난이도는 없을 것 같습니다.

몇 가지 케이스를 통해 성질을 추측합니다.

i 번째 열에서 위를 선택하는 경우
이는 i-1 번째 열에서 아래를 선택하였거나 아무것도 선택하지 않았을 때 가능합니다.

i 번째 열에서 아래를 선택하는 경우
이는 i-1 번째 열에서 위를 선택하였거나 아무것도 선택하지 않았을 때 가능합니다.

i 번째 열에서 아무것도 선택하지 않는 경우
이는 i-1 번째 열에서 어떤 것을 선택했더라도 상관 없습니다. 하지만 2회 연속으로 아무것도 선택하지 않는 것은 최대합을 만족할 수 없으므로 이 경우는 제외할 수 있습니다.

아무것도 선택하지 않는 경우를 고려하지 않는다면 아래와 같은 케이스에서 문제가 발생할 것 입니다.

3
100 0 0
0 0 100

따라서 3가지 경우에 따른 최대합을 구하면서 최종적으로 합의 최대치를 선택하면 됩니다.

import java.io.*;
import java.util.Arrays;

public class Main {
    static int n;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static Integer[][] stickers = new Integer[2][];
    static Integer[][] memo = new Integer[3][100005];// 0: up, 1: down, 2: not

    private static int process() {
        memo[0][0] = stickers[0][0];
        memo[1][0] = stickers[1][0];
        memo[2][0] = 0;

        for (int i = 1; i < n; i++) {
            memo[0][i] = stickers[0][i] + Math.max(memo[1][i - 1], memo[2][i - 1]);
            memo[1][i] = stickers[1][i] + Math.max(memo[0][i - 1], memo[2][i - 1]);
            memo[2][i] = Math.max(memo[0][i - 1], memo[1][i - 1]);
        }
        return Math.max(Math.max(memo[0][n - 1], memo[1][n - 1]), memo[2][n - 1]);
    }

    private static int readInt() {
        try {
            return Integer.parseInt(bufferedReader.readLine());
        } catch (NumberFormatException e) {
            return 0;
        } catch (IOException e) {
            return 0;
        }
    }

    private static Integer[] readInts() {
        try {
            return Arrays.stream(bufferedReader.readLine().split(" "))
                    .map(Integer::parseInt)
                    .toArray(Integer[]::new);
        } catch (NumberFormatException e) {
            return null;
        } catch (IOException e) {
            return null;
        }
    }

    private static void input(){
        n = readInt();
        stickers[0] = readInts();
        stickers[1] = readInts();
    }

    public static void main(String[] args) {
        int t = readInt();

        for (int i = 0; i < t; i++) {
            input();
            System.out.println(process());
        }
    }
}

문제: https://www.acmicpc.net/problem/9465