추가 설명 — 어느 날을 골랐는지 되짚기

동적 계획법 ②는 표를 채워 최대 일급 $15$를 구했다. 표에는 숫자만 있을 뿐, 어느 날을 골랐는지는 어디에도 적혀 있지 않다. 이 글은 채운 표를 거꾸로 읽어 그 구성까지 복원하는 방법을 다룬다.

---

값과 구성은 다르다

본편의 표 r[i][0], r[i][1]에는 각각 $i$일에 쉬었을 때·일했을 때의 최선의 값만 들어 있다. $r[4][1] = 15$는 “4일에 일하는 쪽을 택하면 최대 15를 번다”는 사실만 말해줄 뿐, 그 15를 만든 나머지 선택이 무엇인지는 알려주지 않는다.

값과 구성은 다른 질문이다. $S(n)$을 구하는 점화식은 값만 비교해서 큰 쪽을 고른다. 그 비교가 일어난 자리, 즉 “어느 쪽이 이겼는가”라는 정보는 표를 채우는 동안 이미 결정돼 있다. 표를 지우지만 않으면 그 정보는 그대로 남아 있다. 문제는 이를 어떻게 꺼내느냐다.

---

표를 거꾸로 읽기

방법은 간단하다. 마지막 칸에서 출발해 그 값이 어느 쪽 계산에서 나왔는지 확인하고, 확인된 쪽을 따라 한 칸씩 뒤로 이동한다.

$i$일의 두 칸 중 하나를 방문했다고 하자.

• 방문한 칸이 r[i][1](일함)이면, $i$일은 선택된 날이다. 이 값은 정의상 r[i-1][0] + a[i]이므로, 다음에 봐야 할 칸은 r[i-1][0]이다.
• 방문한 칸이 r[i][0](안 함)이면, $i$일은 선택되지 않았다. 이 값은 max(r[i-1][0], r[i-1][1])이므로, 둘 중 실제로 더 큰 쪽으로 넘어간다. 이 이동은 $i$일을 고른 게 아니라 그저 경유할 뿐이다.

시작은 항상 $\max(r[n][0], r[n][1])$을 낸 칸이고, 끝은 $r[1]$ 아래로 더 내려갈 칸이 없을 때다. 지나온 칸 중 r[i][1]을 방문한 $i$들만 모으면, 그것이 곧 고른 날짜의 집합이다.

---

예시로 되짚기

$a = [3, 5, 6, 10]$으로 채운 표를 다시 보자.

$$r[1] = (0,\ 3), \quad r[2] = (3,\ 5), \quad r[3] = (5,\ 9), \quad r[4] = (9,\ 15)$$

마지막 칸부터 거꾸로 따라간다.

1. $\max(r[4][0]{=}9,\ r[4][1]{=}15) = 15$는 r[4][1]에서 나왔다. 4일 근무를 선택한다. r[4][1] = r[3][0] + a_4이므로 다음은 r[3][0]이다.
2. r[3][0] = 5는 $\max(r[2][0]{=}3,\ r[2][1]{=}5)$의 결과이고, 더 큰 쪽은 r[2][1]이다. 3일은 고른 게 아니라 경유한다. 4일 근무가 3일을 강제로 쉬게 했으니, 3일이 선택지에서 빠지는 건 당연하다. 다음은 r[2][1]이다.
3. r[2][1] = 5는 r[1][0] + a_2에서 나왔다. 2일 근무를 선택한다. 다음은 r[1][0]이다.
4. r[1][0] = 0에 도달했다. 더 내려갈 칸이 없으니 되짚기를 멈춘다.

모아 보면 선택된 날은 $\{2, 4\}$, 합은 $5 + 10 = 15$다. 표의 마지막 칸이 말한 값과 정확히 같다.

---

되짚기를 코드로 옮기기

되짚기 논리를 그대로 함수로 옮기면 다음과 같다.

// r: selectWorkingDays가 채운 2행 표.  고른 날짜를 오름차순으로 돌려준다.
vector<int> reconstruct(const vector<array<int,2>>& r, const vector<int>& a, int n) {
    vector<int> days;
    int i = n;
    bool worked = r[n][1] > r[n][0];   // 마지막 칸에서 함/안 함 중 큰 쪽
    while (i >= 1) {
        if (worked) {                  // i일 근무 → i-1일은 반드시 쉼
            days.push_back(i);
            i -= 2;
            if (i >= 1) worked = r[i][1] > r[i][0];
        } else {                       // i일 쉼 → i-1로
            i -= 1;
            if (i >= 1) worked = r[i][1] > r[i][0];
        }
    }
    reverse(days.begin(), days.end());
    return days;
}

worked가 참이면 $i$일 근무가 확정이라 $i{-}1$일은 자동으로 경유(쉼)이므로 곧장 $i{-}2$로 건너뛴다. 앞서 표를 손으로 짚을 때 거쳤던 “경유” 한 칸을 코드에서는 인덱스 계산으로 흡수한 셈이다. worked가 거짓이면 그 칸은 그저 경유이므로 한 칸만 물러난다.

비교에 >를 쓴 자리가 중요하다. 만약 r[i][1] >= r[i][0]처럼 등호를 넣으면 같은 값일 때 다른 쪽 갈래를 타 다른 선택 집합이 나올 수 있다. 동점에서 어느 쪽을 택할지는 >냐 >=냐로 결정된다.

---

마치며

표는 값을 계산하는 과정에서 구성에 대한 정보도 함께 남긴다. 다만 그 정보를 읽으려면 표를 지우지 않고 마지막 칸부터 거꾸로 따라가야 한다. r[i][1]을 지날 때만 그 날이 선택된 것이고, r[i][0]을 지나는 건 경유일 뿐이다. 이 구분 하나로 값에서 구성을 복원할 수 있다.

동적 계획법 ② →