동적 계획법 ② — 점화식은 어떻게 세우는가

동적 계획법 ①에서는 피보나치로 재귀·메모이제이션·상향식을 봤다. 점화식은 처음부터 주어져 있었다. 이번 편은 점화식이 없는 문제에서 출발해 점화식을 직접 세운다. “마지막 원소를 포함하는가?”라는 결정 하나에서 $S(n) = \max\big(S(n-1),\ S(n-2) + a_n\big)$ 을 유도한다.

이 포스트에서 다루는 내용

결정 기반 점화식 유도: 마지막 날을 포함하는가라는 질문 하나에서 점화식을 뽑아낸다
포함·제외 사례 분석: 두 선택지를 나눠 각각의 최적값을 비교한다
상향식 2행 테이블: 재귀 없이 앞에서부터 채워 답을 구한다
(더 나가면) 선택 복원으로 고른 날짜 되짚기, O(1) 공간으로 줄이기

일할 날짜 고르기

$n$ 일짜리 아르바이트 자리가 있다. $i$ 번째 날의 일급은 $a_i$ 다. 일급은 0 이상이라 하자. 연속된 이틀을 함께 일할 수는 없다. 하루 일하면 다음 날은 쉬어야 한다. 이 조건에서 받을 수 있는 총 일급의 최댓값을 구한다.

예시로 $a = [3,\ 5,\ 6,\ 10]$ (1번째 날부터 4번째 날까지)을 보자. 최댓값은 $15$ 다. 2번째 날( $a_2=5$ )과 4번째 날( $a_4=10$ )을 고르면 두 날이 연속되지 않으면서 합이 $5+10=15$ 로 가장 크다.

모든 경우를 나열해 답을 확인할 수도 있다. 날마다 일하거나 쉬는 두 선택 중 하나이므로 경우의 수는 $2^n$ 에 이른다. 지수 시간이 왜 문제가 되는지는 동적 계획법 ①에서 이미 다뤘다.

그럼 더 빠르게 풀 방법은 없을까? 마지막 날의 선택 하나에 주목하면 길이 보인다.

마지막 날을 포함하는가

$S(n)$ 을 앞 $n$ 일에서 얻을 수 있는 최대 일급으로 정의한다. 구하려는 답은 $S(n)$ 이다.

최적해 하나를 고정해 놓고 그 안에서 $n$ 번째 날을 뜯어본다. 답이 될 자격이 있는 모든 해는 $n$ 번째 날을 포함하거나 포함하지 않거나 둘 중 하나다. 각 경우의 최댓값을 따로 구해 비교하면 된다.

포함(A). 마지막 날을 고르면 $a_n$ 을 그대로 얻는다. 대신 연속 이틀 제약 때문에 $n-1$ 번째 날은 강제로 쉬어야 한다. 쓸 수 있는 날은 앞 $n-2$ 일뿐이고, 그 안에서 최선을 다한 값이 정의상 $S(n-2)$ 다.

A = S(n-2) + a_n

제외(B). 마지막 날을 고르지 않으면 $n-1$ 번째 날에 걸려 있던 제약이 함께 사라진다. 앞 $n-1$ 일을 통째로 자유롭게 최적화한 값이 곧 $S(n-1)$ 이다.

B = S(n-1)

두 경우는 겹치지 않고(마지막 날을 골랐거나 안 골랐거나) 빠짐없다(그 외의 경우는 없다). 최적해는 반드시 둘 중 하나에 속하므로, 답은 두 값 중 더 큰 쪽이다.

S(n) = \max\big(S(n-1),\ S(n-2) + a_n\big)

포함이면 직전 날이 잠기고 S(n-2)+aₙ, 제외면 S(n-1). 둘 중 큰 값이 답이다.

정리 1부분 최적해로부터 전체 최적해가 만들어진다

$S(n-1)$ 과 $S(n-2)$ 가 각각 앞 $n-1$ 일, 앞 $n-2$ 일에서의 최댓값이면

S(n) = \max\big(S(n-1),\ S(n-2) + a_n\big)

이다.

증명. $S(n)$ 을 이루는 최적해 하나를 고정한다. 이 해는 $n$ 번째 날을 포함하거나 포함하지 않는다.

포함하는 경우, 앞 $n-2$ 일에서의 선택은 여전히 자유롭다. 이 부분이 $S(n-2)$ 보다 작다면, 앞 $n-2$ 일만 $S(n-2)$ 를 내는 선택으로 바꿔치기해도 $n-1$ 번째 날은 어차피 잠겨 있으므로 제약이 깨지지 않고 총합은 늘어난다. 이는 처음에 고정한 해가 최적이라는 가정과 어긋난다. 그러므로 포함하는 최적해의 값은 정확히 $S(n-2) + a_n$ 이다.

제외하는 경우도 같은 논법이 선다. 앞 $n-1$ 일에서의 선택이 $S(n-1)$ 보다 작다면 $S(n-1)$ 을 내는 선택으로 바꿔 총합을 키울 수 있어, 역시 최적이라는 가정에 모순이다. 그러므로 제외하는 최적해의 값은 정확히 $S(n-1)$ 이다.

여기까지는 $S(n)$ 이 두 값 중 하나와 같다는 사실만 보인다. 어느 쪽이든 상관없이 $S(n)$ 은 둘 중 작지 않은 쪽, 즉 최댓값과 같아야 한다. 최적해는 포함이든 제외든 둘 중 하나이므로 $S(n) \le \max(S(n-1), S(n-2)+a_n)$ 이다(상계). 거꾸로 두 값은 각각 앞 $n$ 일 문제에서 실제로 만들 수 있는 선택이기도 하다. $S(n-1)$ 을 내는 앞 $n-1$ 일의 선택은 그대로 앞 $n$ 일의 유효한 선택이라 $S(n) \ge S(n-1)$ 이다. $S(n-2)$ 를 내는 선택은 $n-1$ 번째 날을 아예 건드리지 않으므로 $n$ 번째 날을 이어 붙여도 연속 제약이 깨지지 않아 $S(n) \ge S(n-2)+a_n$ 이다(하계). 두 방향을 합치면 $S(n) = \max(S(n-1), S(n-2)+a_n)$ 이다. ∎

기저 조건

점화식은 $S(n-2)$ 까지 거슬러 가므로, 가장 작은 두 경우 $S(0)$ 과 $S(1)$ 은 값을 직접 정한다. 점화식은 $n \ge 2$ 부터 쓴다.

S(0) = 0, \qquad S(1) = a_1

일할 날이 없으면 일급도 없으니 $S(0)=0$ 이다. 하루뿐이면 그날을 고르는 것 말고 다른 도리가 없으니 $S(1)=a_1$ 이다.

상향식으로 채우기

점화식과 기저가 갖춰졌으니 재귀 대신 앞에서부터 채운다. 앞서 나눈 ‘일 함 / 일 안함’ 두 사례를 코드에 그대로 드러내려고, 매 칸에서 두 상태의 최선을 나란히 들고 간다. 1차원 $S$ 배열이나 직전 두 값만으로도 같은 점화식을 계산할 수 있지만, 두 상태를 나누면 각 줄이 어느 사례에서 왔는지 한눈에 보인다.

// a[1..n]: 각 날의 일급.  연속된 두 날은 함께 일할 수 없다.
int selectWorkingDays(const vector<int>& a, int n) {
    if (n == 0) return 0;            // S(0) = 0. 아래는 r[1]을 세우므로 n >= 1이 필요하다
    vector<array<int,2>> r(n + 1);   // r[i][0]: '일 안함', r[i][1]: '일 함' (각자 최선)
    r[1][0] = 0;
    r[1][1] = a[1];

    for (int i = 2; i <= n; i++) {
        r[i][0] = max(r[i-1][0], r[i-1][1]);   // 일 안함 → 전날은 자유
        r[i][1] = r[i-1][0] + a[i];            // 일 함 → 전날은 반드시 쉼
    }
    return max(r[n][0], r[n][1]);
}

내용을 모르면 이 코드가 왜 저렇게 짜였는지 알 수 없다. 줄마다 앞서 세운 사례 분석이 그대로 박혀 있다.

$i$ 일에 안 하는 쪽인 r[i][0]은 전날의 근무 여부를 가리지 않는다. $i$ 일을 비웠으니 $i-1$ 일에 무엇을 했든 연속 제약과 무관하고, 전날 두 선택 중 더 나은 쪽을 그대로 물려받으므로 max(r[i-1][0], r[i-1][1])이다.

r[i][1]이 r[i-1][0]만 참조하는 대목이 핵심이다. $i$ 일에 일하기로 했다면 연속 근무 금지 때문에 $i-1$ 일은 반드시 쉬어야 한다. 전날이 일한 상태였을 가능성은 애초에 답의 후보에서 빠지므로, r[i-1][1]은 쓰지 못하고 r[i-1][0]에 $a_i$ 를 더한 값만 남는다. 앞서 유도한 $A = S(n-2) + a_n$ 이 여기서는 “전날은 안 함” 한 줄로 압축된 셈이다.

두 줄을 합치면 앞서 본 1차원 정의와 바로 대응된다.

S(i) = \max\big(r[i][0],\ r[i][1]\big)

$r[i][0]$ 과 $r[i][1]$ 은 $i$ 번째 날의 선택으로 갈린 두 갈래일 뿐, 둘을 합친 최댓값은 정확히 $S(i)$ 다. 함수가 끝에서 max(r[n][0], r[n][1])을 돌려주는 이유도 이것이다.

$a = [3,\ 5,\ 6,\ 10]$ 으로 표를 채워 본다. ‘일 안함’ 행은 $0, 3, 5, 9$ , ‘일 함’ 행은 $3, 5, 9, 15$ 로 채워지고, 마지막 칸의 최댓값 $15$ 가 답이다. 값을 되짚으면 ‘일 함’ 행이 앞의 ‘일 안함’ 행에서 넘어온 지점, 즉 2번째 날과 4번째 날을 고른 경로가 드러난다.

일급 [3,5,6,10]을 왼쪽부터 채운다. '일 함'/'일 안함' 두 줄을 이어 계산해 마지막 칸에서 최댓값 15가 나오고, 되짚으면 2·4일을 고른 것이다.

칸마다 하는 일은 덧셈과 비교 한 번씩, 상수 시간이다. 칸은 $n$ 개뿐이라 전체는 $O(n)$ 시간이다. 표 두 줄을 그대로 들고 있으니 공간도 $O(n)$ 이다.

더 나가면

채운 표를 거꾸로 읽으면 어느 날을 골랐는지까지 복원된다. 그 되짚기 방법은 추가 설명 — 어느 날을 골랐는지 되짚기에서 다룬다.

점화식 $S(n) = \max(S(n-1), S(n-2)+a_n)$ 은 직전 두 값만 참조하므로, 표 전체 대신 변수 두 개만 굴려도 $O(1)$ 공간으로 답이 나온다. 값만 한 번 훑어 구하는 이 방식에서는 지나간 칸이 남지 않아 곧바로 되짚을 수 없다.

마치며

이번 편은 점화식이 없는 문제에서 점화식을 세우는 과정을 봤다. DP①이 이미 있는 점화식을 계산했다면, DP②는 “마지막 원소를 포함하는가”라는 결정 하나로 점화식 자체를 유도했다. 포함과 제외로 사례를 가르고, 두 경우가 겹치지 않고 빠짐없다는 사실만으로 $S(n) = \max(S(n-1), S(n-2)+a_n)$ 이 나왔다.

같은 결정 사고는 원소 하나가 아니라 구간으로도 확장된다. “이 구간을 어디서 나눌 것인가”라는 결정이 다음 편의 주제고, 그 대표적인 무대가 행렬 곱셈의 곱셈 순서(구간 DP)다.

동적 계획법 ① →