백준 9465 스티커 Java: 위·아래 선택을 나누는 DP

백준 9465번 ‘스티커’는 2×N grid에서 한 sticker를 떼면 상하좌우로 붙은 sticker를 고를 수 없을 때 점수 합의 최댓값을 구한다. 현재 column의 위를 고를지 아래를 고를지에 따라 이전 column에서 허용되는 상태가 달라진다.

• 백준 9465번 스티커

점화식

top[i]를 i번째 column의 위 sticker를 반드시 고른 최대 점수, bottom[i]를 아래 sticker를 반드시 고른 최대 점수라고 하자.

위 sticker를 고르면 바로 왼쪽 위는 고를 수 없다. 이전 column의 아래를 골랐거나, 한 column을 건너뛰고 그 이전까지의 최적 상태에서 올 수 있다.

top[i] = scoreTop[i]
         + max(bottom[i - 1], bottom[i - 2])

bottom[i] = scoreBottom[i]
            + max(top[i - 1], top[i - 2])

앞에 0 padding 두 칸을 두면 i = 2부터 같은 식을 적용할 수 있다.

Java 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int testCount = Integer.parseInt(reader.readLine());
        StringBuilder output = new StringBuilder();

        for (int test = 0; test < testCount; test++) {
            int columnCount = Integer.parseInt(reader.readLine());
            int[][] score = new int[2][columnCount + 2];

            for (int row = 0; row < 2; row++) {
                StringTokenizer tokenizer = new StringTokenizer(
                        reader.readLine()
                );
                for (int column = 2; column < columnCount + 2; column++) {
                    score[row][column] = Integer.parseInt(
                            tokenizer.nextToken()
                    );
                }
            }

            int[] top = new int[columnCount + 2];
            int[] bottom = new int[columnCount + 2];

            for (int column = 2; column < columnCount + 2; column++) {
                top[column] = score[0][column] + Math.max(
                        bottom[column - 1],
                        bottom[column - 2]
                );
                bottom[column] = score[1][column] + Math.max(
                        top[column - 1],
                        top[column - 2]
                );
            }

            int last = columnCount + 1;
            output.append(Math.max(top[last], bottom[last])).append('\n');
        }

        System.out.print(output);
    }
}

원문 code의 행이 뒤바뀐 부분

원문 점화식 설명은 위 sticker score를 top에 더하는 형태였지만 실제 code에서는 dp[0]에 아래쪽 arr[1]을 더하고 dp[1]에 위쪽 arr[0]을 더했다. 두 row가 완전히 대칭이라 최종 max가 맞을 수는 있어도 이름과 값이 반대로 저장되어 읽기 어렵다. 새 code는 state 이름과 score row를 일치시켰다.

각 column의 두 state를 상수 시간에 구하므로 test case별 시간은 O(N), 배열 공간은 O(N)이다. 이전 두 column만 보존하면 공간을 O(1)로 줄일 수도 있다.

손으로 조합을 그려 본 30분

원문에는 가능한 선택을 손으로 그리며 DP라는 느낌을 잡는 데 약 20분, code 작성에 약 10분이 걸린 것으로 추정한다고 적혀 있다. 제출 뒤 System.out.println과 StringBuilder version의 시간이 776ms와 900ms로 달라 이유를 찾아봤고, 재실행 결과 server 상황에 따른 변동일 수 있다고 판단했다.

그 해석이 맞다. 단일 online judge 측정은 controlled benchmark가 아니다. 여러 test case의 output을 한 번에 모으면 system call 수를 줄일 수 있다는 구조적 이유로 StringBuilder를 쓰되, 한두 번의 ms 차이를 일반 성능 결론으로 확대하지 않는다.

다른 two-choice rolling state는 백준 1149 RGB거리에서 이어진다.

검증 범위

Java source를 수동 검토하고 column 1·2, 한쪽 행만 큰 경우와 작은 random 2×N score를 모든 valid sticker subset과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.