[PAST] Part 2 — 동적 계획법 심화 ① (動的計画法 発展)

개요

동적 계획법(Dynamic Programming)은 주어진 문제 전체를 일련의 부분 문제로 잘 분해한 뒤, 각 부분 문제에 대한 해를 메모해 가며 순서대로 구해 나가는 기법입니다. 범용성이 매우 높아 컴퓨터 과학의 이론적인 문제부터 현실 세계의 최적화 문제까지 폭넓게 쓰이며, PAST에서도 즐겨 출제됩니다.

동적 계획법으로 문제를 풀 때 중요한 것은, 원래 문제를 분해해서 얻은 무수한 소문제를 어떻게 묶어서 부분 문제를 구성할 것인가입니다. 해법 패턴이 무한정 많다고 생각하기 쉽지만, "부분 문제로 나누는 방법"에 주목하면 알려진 패턴은 의외로 적습니다.

이번 파트에서는 그 출발점이 되는 가장 기본적인 분할 방식 — "N개 중 앞에서 $i$개까지"를 부분 문제로 잘라내는 DP — 를 배낭 문제로 복습한 뒤, 같은 사고방식이 겉보기에 전혀 다른 문제들에도 그대로 통한다는 것을 세 개의 예제로 확인합니다.

다루는 주제

2.1 동적 계획법의 복습 (배낭 문제)

먼저 동적 계획법의 사고방식을 복습합니다. 소재는 배낭 문제(ナップサック問題)입니다. 입문서에서 이미 다루는 고전적인 문제지만, 배낭 문제를 푸는 사고방식은 다른 많은 문제에도 그대로 유효하기 때문에 복습할 가치가 충분합니다.

예제 2-1-1: ナップサック問題 (AtCoder Educational DP Contest · D문제)

문제 요약

• $N$개의 품목이 있고, 품목 $i$의 무게는 $w_i$, 가치는 $v_i$ ($0 \leq i \leq N-1$)
• $N$개 중 몇 개를 골라 배낭에 넣어 가져가되, 넣은 품목의 무게의 총합은 $W$ 이하여야 함
• 배낭에 넣은 품목의 가치의 총합의 최댓값을 구하라
• 제약: $1 \leq N \leq 100$, $1 \leq W \leq 10^5$, $1 \leq w_i \leq W$, $1 \leq v_i \leq 10^9$

사고 과정

전탐색의 한계: 각 품목에 대해 "넣는다 / 넣지 않는다" 두 가지이므로 전체 $2^N$가지의 선택지가 있습니다. $N \leq 100$이라는 제약에서는 전탐색이 불가능합니다.

갑자기 $N$개 전체를 생각하는 것은 어려우므로, 다음과 같이 앞에서부터 하나씩 늘려 가며 생각합니다.

1. 0개의 품목에 대한 부분 문제를 풀고,
2. 그 결과를 활용하여 1개의 품목에 대한 부분 문제를 풀고,
3. 그 결과를 활용하여 2개의 품목에 대한 부분 문제를 풀고, …
4. 그 결과를 활용하여 원래의 $N$개 품목에 대한 문제를 푼다.

먼저, 실패하는 정의부터

가장 먼저 떠오르는 배열은 아마 이것일 겁니다.

dp[i] ← 번호가 작은 i개의 품목(품목 0, 1, ..., i-1)만 고려하여,
        무게의 총합이 W 이하가 되도록 몇 개 골랐을 때 가치의 총합의 최댓값

하지만 이 정의로는 dp[i]의 값으로부터 dp[i+1]의 값을 구할 수 없습니다. "무게의 총합이 $W$ 이하인 범위에서 고른 가치의 최댓값"만 알고 있으면, 거기에 다음 품목을 더 넣었을 때 무게가 $W$를 넘는지 아닌지를 알 수 없기 때문입니다.

수정한 정의

dp[i][j] ← 번호가 작은 i개의 품목(품목 0, 1, ..., i-1)만 고려하여,
           무게의 총합이 정확히 j가 되도록 몇 개 골랐을 때 가치의 총합의 최댓값
           (무게의 총합을 j로 만들 수 없는 경우는 -∞)

dp[i+1][j]를 구하기 위해, 품목 $i$를 고르는지 여부로 경우를 나눕니다.

품목 $i$를 고르지 않는 경우 — "품목 $0, 1, \ldots, i-1$ 중에서 무게의 총합이 $j$가 되도록 고른 가치의 최댓값"과 일치하므로,

$$dp[i+1][j] = dp[i][j]$$

품목 $i$를 고르는 경우 — "품목 $0, 1, \ldots, i-1$ 중에서 무게의 총합이 $j - w_i$가 되도록 고른 가치의 최댓값"에 $v_i$를 더한 값과 일치하므로,

$$dp[i+1][j] = dp[i][j - w_i] + v_i$$

단, 이쪽은 $j \geq w_i$일 때만 유효하다는 점에 주의합시다.

알고리즘 정리

1. dp[i+1][j]의 값을 미리 $-\infty$로 초기화해 둔다
2. dp[i+1][j] = max(dp[i+1][j], dp[i][j]) 로 갱신한다
3. $j \geq w_i$인 경우, dp[i+1][j] = max(dp[i+1][j], dp[i][j - w[i]] + v[i]) 로 갱신한다

배열 dp의 첨자 조합이 $(N+1)(W+1)$개이므로, 계산량은 $O(NW)$로 평가할 수 있습니다. $N \leq 100$, $W \leq 10^5$이므로 약 $10^7$회 — 충분히 제한 시간 안에 들어옵니다.

Java 구현 예시

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] w = new int[N];
        long[] v = new long[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Long.parseLong(st.nextToken());
        }

        // 「그 무게는 만들 수 없다」를 나타내는 값. v[i] 를 더해도 여전히 압도적으로 작다
        final long NEG = -(1L << 60);

        // dp[i][j] = 앞의 i개만 고려해 무게의 총합이 정확히 j일 때 가치의 최댓값
        long[][] dp = new long[N + 1][W + 1];
        for (long[] row : dp) Arrays.fill(row, NEG);
        dp[0][0] = 0;   // 0개를 골라 무게 0 → 가치 0

        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= W; j++) {
                // 품목 i 를 고르지 않는 경우
                dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);

                // 품목 i 를 고르는 경우
                if (j >= w[i]) {
                    dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
                }
            }
        }

        // 무게의 총합이 W 「이하」이면 되므로, 마지막 행 전체에서 최댓값을 고른다
        long ans = 0;
        for (int j = 0; j <= W; j++) ans = Math.max(ans, dp[N][j]);
        System.out.println(ans);
    }
}

long[] dp = new long[W + 1];
Arrays.fill(dp, NEG);
dp[0] = 0;

for (int i = 0; i < N; i++) {
    // j 를 역순으로 — 같은 품목을 두 번 담는 것을 막는다
    for (int j = W; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

2.1절 정리

• 배낭 문제에서는 $N$개의 품목 각각에 대해 "넣는다"와 "넣지 않는다"의 2가지가 있으므로, 전체적으로 $2^N$가지의 선택 방법이 고려됩니다.
• $2^N$가지의 선택 방법이 고려되는 문제에서는, "처음 $i$개의 품목에 대한 문제"를 부분 문제로 잘라내는 동적 계획법이 종종 유효합니다.

2.2 이전 정보를 유지하며 진행하는 동적 계획법

배낭 문제를 푸는 동적 계획법의 사고방식은 극도로 범용성이 높아, 다양한 문제를 해결하는 데 도움이 됩니다. 그 사고방식이란

1. 0개에 대한 부분 문제를 풀고,
2. 그 결과를 활용하며 1개에 대한 부분 문제를 풀고,
3. 그 결과를 활용하며 2개에 대한 부분 문제를 풀고, …
4. 그 결과를 활용하며 원래의 $N$개에 대한 문제를 푼다

는, 부분 문제를 순서대로 풀어 나가는 방식입니다. 실은 동적 계획법으로 풀리는 문제의 다수가 이와 유사한 사고방식으로 풀립니다. 그것을 보이기 위해 세 개의 예제를 풀어 봅시다.

공통 템플릿

이 절에서 다루는 문제들은 모두 다음 형태의 배열로 정리됩니다.

dp[i][(어떤 상태)] ← N개의 것 중 처음 i개에 대한 부분 문제를 생각하고,
                    그때 (어떤 상태)가 되는 경우에 대한 답

(어떤 상태) 부분을 궁리하는 것만으로 수많은 문제를 해결할 수 있습니다. 세 예제에서 이 자리에 무엇이 들어가는지를 눈여겨보시기 바랍니다.

예제 2-2-1: AtCounter (競プロ典型90問 · 008)

문제 요약

• 길이 $N$의 문자열 $S$가 주어짐
• $S$에서 몇 글자를 뽑아내는 방법은 $2^N$가지
• 그중 뽑아낸 글자를 그 순서대로 나열했을 때 "atcoder"가 되는 것이 몇 가지인지 구하라
• 단, $10^9 + 7$로 나눈 나머지로 답할 것
• 제약: $1 \leq N \leq 10^6$, $S$는 영소문자로 이루어진 길이 $N$의 문자열

사고 과정

배낭 문제와 마찬가지로, 이번 문제도 "$2^N$가지의 경우를 탐색하고 싶다"는 형식의 문제입니다. 그러한 문제에서는 배낭 문제와 같은 형태의 동적 계획법이 유효한 경우가 많습니다.

이번에 부가해야 할 정보는 "목표 문자열 "atcoder"의 몇 번째 글자까지 일치시켰는가"입니다.

dp[i][j] ← 문자열 S의 처음 i글자에서 몇 글자를 뽑아 이어 붙이는 방법 중,
           그것이 "atcoder"의 처음 j글자와 정확히 일치하는 방법의 개수

초기 조건은 dp[0][0] = 1(아무것도 뽑지 않으면 빈 문자열 하나)이고, 구하려는 답은 dp[N][7]입니다. 문자열 $T = $ "atcoder"라 하면, 갱신은 두 갈래입니다.

문자 $S_i$를 뽑지 않는 경우

$$dp[i+1][j] \leftarrow dp[i+1][j] + dp[i][j]$$

문자 $S_i$를 뽑는 경우 — $S_i = T_{j-1}$일 때만 가능합니다.

$$dp[i+1][j] \leftarrow dp[i+1][j] + dp[i][j-1]$$

손으로 따라가 보기

감을 잡기 위해, 목표 문자열을 "atc"로 줄이고 $S = $ "aatctc"로 두고 표를 채워 봅시다.

답은 6입니다. 실제로 $S$의 a는 1·2번째, t는 3·5번째, c는 4·6번째에 있으므로 $(a, t, c)$의 조합은 $(1,3,4), (1,3,6), (1,5,6), (2,3,4), (2,3,6), (2,5,6)$의 6가지 — 표와 일치합니다.

Java 구현 예시

$N \leq 10^6$이므로 2차원 배열을 그대로 잡으면 수십 MB가 날아갑니다. dp[i+1]이 dp[i]만을 참조하므로, $j$를 큰 쪽부터 도는 1차원 갱신으로 접습니다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        String S = br.readLine().trim();

        final int MOD = 1_000_000_007;
        final String T = "atcoder";
        final int M = T.length();   // 7

        // dp[j] = 지금까지 본 글자들로 T의 처음 j글자를 만드는 방법의 수
        long[] dp = new long[M + 1];
        dp[0] = 1;

        for (int i = 0; i < N; i++) {
            char c = S.charAt(i);

            // j 를 역순으로 — dp[j-1] 이 아직 「이번 글자를 쓰기 전」의 값이어야 한다
            for (int j = M; j >= 1; j--) {
                if (c == T.charAt(j - 1)) {
                    dp[j] = (dp[j] + dp[j - 1]) % MOD;
                }
            }
        }

        System.out.println(dp[M]);
    }
}

예제 2-2-2: 部活のスケジュール表 (일본정보올림픽 예선 2014 · D문제)

문제 요약

• 프로그래밍부에는 J군·O군·I군 3명의 부원이 있고, $N$일간의 활동 스케줄(각 날짜에 3명 중 누가 참가하는지)을 정하려 함
• 각 활동일의 스케줄은 부원별로 참가 여부 2가지 → 전체 8가지
• 부실 열쇠는 단 하나이며 처음에는 J군이 가지고 있음. 각 활동일에는 그날 참가하는 부원 중 누군가 1명이 열쇠를 가지고 있어야 하고, 활동 후 참가한 부원 중 누군가가 열쇠를 가지고 돌아감
• 활동일에는 매번 반드시 활동이 이루어지도록 각 활동일의 책임자가 미리 정해져 있으며, 책임자는 반드시 그날 출석해야 함
• 조건을 만족하는 스케줄의 경우의 수를 10007로 나눈 나머지로 구하라
• 제약: $2 \leq N \leq 1000$, $S$는 J, O, I로 이루어진 길이 $N$의 문자열

사고 과정 ① — 문제를 시각적으로 정리한다

문제문이 다소 복잡하므로, 먼저 $3 \times N$ 격자를 흑백으로 칠하는 문제로 바꿔 말합니다. 위에서 $0$행(J) / $1$행(O) / $2$행(I), 왼쪽에서 $d$열이 $d$일째를 뜻하고, 검은 칸 = 그 부원이 그날 참가로 둡니다. 그러면 조건은 다음 두 줄로 압축됩니다.

• 왼쪽 위 칸은 검게 칠해져 있다 (처음에 J군이 열쇠를 가지고 있음)
• 연속하는 어느 2열에 대해서도, 둘 다 검게 칠해진 행이 적어도 하나 존재한다 (열쇠를 넘겨줄 수 있음)

여기에 "각 열에는 그날의 책임자에 해당하는 행이 반드시 검다"는 조건이 더해집니다.

사고 과정 ② — 집합을 정수로 표현하기

각 열의 상태는 "어느 부원들이 참가하는가"라는 집합입니다. 집합을 배열 첨자로 쓰려면 정수로 바꿔야 합니다.

DP 정의

먼저 "$d$열까지 칠하는 문제"를 부분 문제로 잘라내 dp[d]를 생각하고 싶지만, 그것만으로는 "$d-1$열과 $d$열에 좌우로 인접한 검은 칸이 있는가"를 판정할 수 없습니다. 그래서 직전 열의 칠해진 방식을 첨자로 부가합니다.

dp[d][S] ← 왼쪽에서 d열(열 0, 1, ..., d-1)에 대해, 마지막 열 d-1에서
           검게 칠하는 칸의 행 번호의 집합이 정수 S가 되도록 한 뒤,
           조건을 만족하도록 흑백으로 칠하는 경우의 수

초기 조건은 dp[0][1 << 0] = 1입니다. "가상의 $-1$열에서 J군만 검다" — 즉 처음에 J군이 열쇠를 가지고 있다는 사실을 그대로 옮긴 것입니다.

갱신은 직전 열의 상태 $T$로 경우를 나눕니다. 정수 $S$가 나타내는 집합과 정수 $T$가 나타내는 집합이 공통 원소를 가질 때,

$$dp[d+1][S] = (dp[d+1][S] + dp[d][T]) \bmod 10007$$

Java 구현 예시

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        String responsible = br.readLine().trim();

        final int MOD = 10007;

        // dp[d][S] = 왼쪽 d열까지 칠했고, d-1 열에서 검게 칠한 행의 집합이 S인 경우의 수
        int[][] dp = new int[N + 1][8];
        dp[0][1 << 0] = 1;   // 가상의 -1열: J군만 검정 = 처음에 J군이 열쇠를 가짐

        for (int d = 0; d < N; d++) {
            char r = responsible.charAt(d);

            for (int S = 0; S < 8; S++) {
                // d 열은 그날의 책임자를 반드시 포함해야 한다
                if (r == 'J' && (S & (1 << 0)) == 0) continue;
                if (r == 'O' && (S & (1 << 1)) == 0) continue;
                if (r == 'I' && (S & (1 << 2)) == 0) continue;

                // d-1 열의 칠해진 방식으로 경우를 나눈다
                for (int T = 0; T < 8; T++) {
                    // 좌우로 검은 칸이 인접한 곳이 있는가 = 열쇠를 넘길 수 있는가
                    if ((S & T) != 0) {
                        dp[d + 1][S] = (dp[d + 1][S] + dp[d][T]) % MOD;
                    }
                }
            }
        }

        int ans = 0;
        for (int S = 0; S < 8; S++) ans = (ans + dp[N][S]) % MOD;
        System.out.println(ans);
    }
}

$S$와 $T$가 각각 8가지이므로 갱신 1회의 비용은 상수, 전체 계산량은 $O(N)$입니다.

예제 2-2-3: 括弧 (제2회 PAST · K문제)

문제 요약

• (와 )로 이루어진 길이 $N$의 문자열 $S$가 주어짐
• 먼저 다음 조작을 0회 이상 원하는 만큼 수행 — 어떤 $i$를 골라 $S_i$가 (이면 )로, )이면 (로 변경. 비용은 $C_i$
• 그 후 다음 조작을 1회 수행 — $S$에서 0글자 이상 골라 삭제(전부 삭제해도 좋음)하고, 삭제하지 않은 글자를 원래 순서로 이어 붙임. $S$의 $i$번째 글자를 삭제하는 비용은 $D_i$
• $S$를 괄호의 대응이 맞는 문자열로 만들기 위한 합계 비용의 최솟값을 구하라
• 제약: $1 \leq N \leq 3000$, $1 \leq C_i, D_i \leq 10^9$

사고 과정 ① — 조건을 다루기 쉽게 바꿔 말한다

"어떤 조건을 만족시키기 위한 최소 비용을 구하라" 형식의 문제에서는, 조건을 알기 쉽게 바꿔 말하는 것이 중요합니다. "괄호의 대응이 맞는다"는 조건은 재귀적으로 정의되어 있어 그대로는 다루기 어렵습니다.

그래서 다음 값을 생각합니다.

H_i ← 문자열 S의 선두부터 i글자째까지에서,
      문자 '(' 의 개수에서 문자 ')' 의 개수를 뺀 값

정합적인 괄호열에서는 (와 )가 대응하므로 최종적으로 $H_N = 0$이 되어야 합니다. 하지만 그것만으로는 충분조건이 아닙니다. 예컨대 $S = $ ")("는 $H_N = 0$이지만 정합적이지 않습니다. (에 대응하는 )는 반드시 (보다 오른쪽에 있어야 하기 때문입니다. 따라서 필요한 조건은 다음 둘입니다.

• $H_i \geq 0 \quad (i = 1, \ldots, N)$
• $H_N = 0$

역으로 이 둘을 만족하면 어느 (에도 )를 대응시킬 수 있으므로, 이는 괄호열이 정합적이기 위한 필요충분조건입니다. 다루기 쉬운 조건으로 바꿔 말하는 데 성공했습니다.

예를 들어 $S = $ "(()(()))()"에 대해 $H_i$를 늘어놓으면 다음과 같습니다. 한 번도 0 아래로 내려가지 않고 마지막에 0으로 돌아옵니다.

사고 과정 ② — DP 정의

dp[i][j] ← 문자열 S의 선두부터 i글자에 대해 문제문에 정의된 조작을 반복하여,
           H_1, H_2, ..., H_{i-1} ≥ 0 이고 H_i = j 인 상태로 만들기 위한 최소 비용

답은 dp[N][0]이고, 초기 조건은 dp[0][0] = 0입니다. dp[i]의 값으로 dp[i+1]을 갱신하는 식을 세 갈래로 나눠 생각합니다.

$S_i$에 변경을 가하지 않는 경우 — 비용을 지불하지 않습니다.

• $S_i = $ ( 일 때, dp[i+1][j] = min(dp[i+1][j], dp[i][j-1]) ($j > 0$일 때만)
• $S_i = $ ) 일 때, dp[i+1][j] = min(dp[i+1][j], dp[i][j+1])

$S_i$를 변경하는 경우 — $C_i$만큼 비용을 지불합니다.

• $S_i = $ ( 일 때, dp[i+1][j] = min(dp[i+1][j], dp[i][j+1] + C[i])
• $S_i = $ ) 일 때, dp[i+1][j] = min(dp[i+1][j], dp[i][j-1] + C[i]) ($j > 0$일 때만)

$S_i$를 삭제하는 경우 — $D_i$만큼 비용을 지불하며, $H$는 움직이지 않습니다.

• 어느 쪽이든 dp[i+1][j] = min(dp[i+1][j], dp[i][j] + D[i])

배열 dp[i][j]의 크기가 $O(N^2)$이므로, 이 해법의 계산량은 $O(N^2)$입니다. $N \leq 3000$이므로 약 $9 \times 10^6$회 — 충분합니다.

Java 구현 예시

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        String S = br.readLine().trim();
        long[] C = readLongs(br, N);
        long[] D = readLongs(br, N);

        // C, D 가 각각 최대 1e9, 글자가 최대 3000개이므로 합계는 6e12 — long 이 필요하다
        final long INF = Long.MAX_VALUE / 4;

        // cur[j] = 앞의 i글자를 처리해 H가 한 번도 음수가 되지 않고 현재 H = j 인 최소 비용
        long[] cur = new long[N + 1];
        long[] next = new long[N + 1];
        Arrays.fill(cur, INF);
        cur[0] = 0;

        for (int i = 0; i < N; i++) {
            Arrays.fill(next, INF);
            char c = S.charAt(i);

            for (int j = 0; j <= N; j++) {
                // ① S[i] 에 아무것도 하지 않는 경우
                if (c == '(' && j > 0) next[j] = Math.min(next[j], cur[j - 1]);
                if (c == ')' && j < N) next[j] = Math.min(next[j], cur[j + 1]);

                // ② S[i] 를 변경하는 경우 (비용 C[i])
                if (c == '(' && j < N) next[j] = Math.min(next[j], cur[j + 1] + C[i]);
                if (c == ')' && j > 0) next[j] = Math.min(next[j], cur[j - 1] + C[i]);

                // ③ S[i] 를 삭제하는 경우 (비용 D[i]) — H 는 그대로
                next[j] = Math.min(next[j], cur[j] + D[i]);
            }

            long[] tmp = cur; cur = next; next = tmp;
        }

        System.out.println(cur[0]);
    }

    private static long[] readLongs(BufferedReader br, int n) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
        return a;
    }
}

2.2절 정리

• 2.2절에서 다룬 문제는 어느 것이나 "$N$개의 것 중 선두에서 $i$ $(= 0, 1, \ldots, N)$개까지를 꺼낸 부분 문제"를 순서대로 생각해 가는 동적 계획법으로 해결할 수 있었습니다.
• 동적 계획법의 갱신식을 만들기 위해, 각 부분 문제에 필요한 정보를 부가했습니다.

정리

이번 파트에서 다룬 네 문제는 겉모습이 전부 다르지만, "앞에서 $i$개"라는 같은 축 위에 서 있습니다. 달랐던 것은 무엇을 첨자로 들고 갔는가뿐입니다.

실전 팁

1. $2^N$ 또는 $a^N$가지의 선택지가 보이면 "앞에서 $i$개까지"를 부분 문제로 잘라낼 수 있는지 먼저 의심합니다.
2. 점화식이 서지 않으면 정의가 틀린 것이 아니라 정보가 부족한 것입니다. "다음 한 칸을 갱신하려면 무엇을 더 알아야 하는가"를 묻고, 그 답을 첨자로 추가합니다.
3. 다루기 어려운 조건(괄호의 정합성 등)은 단조로운 수치 조건으로 바꿔 말하고, 가능하면 그 조건을 첨자의 범위 자체로 흡수합니다.
4. dp[i+1]이 dp[i]만을 본다면 1차원 롤링 배열로 접을 수 있습니다. 이때 첨자를 도는 방향(역순)이 정확성을 좌우합니다.
5. Java로 옮길 때는 제약의 곱을 먼저 암산해 int/long과 INF의 여유를 정합니다. Python 코드를 그대로 번역하면 오버플로로 조용히 틀립니다.

관련 문제 링크

참고 자료

• 서적: 「アルゴリズム実技検定 公式テキスト ［上級］～［エキスパート］編」 (マイナビ出版, 2023) — 제2장 2.1~2.2절
• 소스코드: tsutaj/pastbook-2-source-code (Github)
• Educational DP Contest: https://atcoder.jp/contests/dp
• 競プロ典型90問: https://atcoder.jp/contests/typical90
• PAST 공식 사이트: https://past.atcoder.jp
• AtCoder 공식 사이트: https://atcoder.jp