[PAST] Part 2 보충 — 部活のスケジュール表 문제 풀이

이 글을 쓰는 이유

본편에서 이 문제는 "집합을 첨자로 들고 가는 예"로 지나갔습니다. 격자로 바꿔 말하고, 집합을 정수로 표현하고, 점화식을 쓰고, Java 구현을 붙이는 데까지가 전부였습니다.

그런데 이 문제의 코드를 처음 읽으면, 이해가 막히는 지점이 대부분 점화식이 아닌 곳에 있습니다.

• dp[0][1 << 0] = 1 — 이 한 줄은 대체 무엇을 선언한 것인가? "가상의 $-1$열"이라는 말은 무슨 뜻인가?
• 답이 왜 dp[N][S] 전체의 합인가? 배낭 문제에서는 마지막 행의 최댓값이었는데, 무엇이 달라진 것인가?
• S & T != 0이 "열쇠를 넘겨줄 수 있다"와 같은 말인 이유는 무엇인가?
• 부원이 3명이라 상태가 8가지였다. $K$명이면 이 풀이는 어디서부터 터지는가?

이 글은 그 네 가지에 답합니다. 본편과 겹치는 부분은 2절에서 압축하고 넘어가겠습니다.

1. 문제를 다시 읽는다 — 조건을 그림으로 바꾼다

프로그래밍부에 J군·O군·I군 세 명이 있고, $N$일간의 활동 스케줄(각 날짜에 누가 참가하는지)을 정합니다. 부실 열쇠는 하나뿐이고 처음에는 J군이 가지고 있습니다. 각 활동일에는 그날 참가하는 부원 중 누군가가 열쇠를 가지고 있어야 하며, 활동이 끝나면 참가한 부원 중 누군가가 열쇠를 가지고 돌아갑니다. 여기에 "각 날의 책임자는 반드시 출석한다"가 붙습니다. 조건을 만족하는 스케줄의 개수를 $10007$로 나눈 나머지로 구합니다.

1편에서와 같이, 문제문 아래의 제약 네 줄부터 읽습니다.

열쇠 조건을 "집합이 만난다"로 바꾼다

이 문제의 전부는 사실 딱 한 번의 바꿔 말하기에 있습니다. 열쇠 규칙은 문장으로 읽으면 복잡합니다.

각 활동일에는 그날 참가하는 부원 중 누군가 1명이 열쇠를 가지고 있어야 하고, 활동 후 참가한 부원 중 누군가가 열쇠를 가지고 돌아간다.

$d$일차에 참가하는 부원의 집합을 $A_d$라고 둡시다. 열쇠는 $d-1$일차가 끝날 때 $A_{d-1}$에 속한 누군가가 가지고 돌아갔습니다. 그리고 $d$일차에는 $A_d$에 속한 누군가가 그 열쇠를 가지고 있어야 합니다. 열쇠는 하나뿐이므로, 이 두 조건이 동시에 성립하려면

$$A_{d-1} \cap A_d \neq \emptyset$$

이어야 합니다. 역으로 이 교집합이 비어 있지 않다면, 거기 속한 사람 한 명을 골라 열쇠를 맡기면 됩니다. 즉 이 교집합 조건은 열쇠 규칙의 필요충분조건입니다. "누가 열쇠를 가졌는가"를 끝까지 추적할 필요가 없어졌습니다.

그러면 문제 전체가 세 줄로 압축됩니다.

본편이 $3 \times N$ 격자의 흑백 칠하기로 그린 것이 바로 이것입니다. 행이 부원, 열이 날짜, 검은 칸이 참가입니다.

이 그림에서 "$A_{d-1} \cap A_d \neq \emptyset$"은 이웃한 두 열에 검은 칸이 가로로 맞닿은 행이 적어도 하나 있다로 보입니다. 위 예에서 0–1열은 J행에서, 1–2열은 I행에서, 2–3열은 O행에서 맞닿아 있습니다. 조건을 만족합니다.

2. 본편 요약 — 여기까지는 이미 한 이야기

본편에서 세운 정의와 갱신식만 옮겨 둡니다. 자세한 유도는 본편 2.2절을 봐 주세요.

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

• 집합을 정수로 — J = 1 << 0, O = 1 << 1, I = 1 << 2. 집합 $\{$J, O$\}$는 이진법 011, 즉 3
• 초기 조건 — dp[0][1 << 0] = 1
• 갱신 — $S$가 그날의 책임자를 포함하고, 또 (S & T) != 0일 때 $dp[d+1][S] \mathrel{+}= dp[d][T]$
• 답 — 마지막 행 전체의 합 $\sum_S dp[N][S]$
• 계산량 — $O(N)$ (정확히는 $8 \times 8 \times N = 64N$)

3. dp[0][1 << 0] = 1은 무엇을 선언한 것인가

이 문제에서 가장 자주 막히는 한 줄입니다. 정의를 그대로 대입해 봅시다. $d = 0$은 "왼쪽에서 0개의 열을 칠했다"는 뜻입니다. 그런데 정의는 "마지막 열 $d-1$에서 검게 칠한 행의 집합이 $S$"라고 말합니다. $d = 0$이면 그 마지막 열은 $-1$열, 즉 존재하지 않는 열입니다.

그래서 없는 열을 하나 만들어 냅니다. 격자 왼쪽에 $-1$열을 덧붙이고, 거기에 J군만 검게 칠해 둔 것으로 칩니다.

이렇게 두면 무슨 일이 벌어지는지 보세요. $-1$열과 0열 사이에도 똑같은 인접 조건을 걸면,

$$\{\text{J}\} \cap A_0 \neq \emptyset \iff \text{J} \in A_0$$

가 됩니다. 이것은 1절에서 정리한 세 번째 조건 — "처음에 J군이 열쇠를 가지고 있다" — 과 정확히 같은 말입니다.

// 가상 열을 쓰지 않은 경우 — 첫날을 따로 처리해야 한다
int need = 1 << "JOI".indexOf(responsible.charAt(d));

for (int S = 0; S < 8; S++) {
    if ((S & need) == 0) continue;

    if (d == 0) {
        // 첫날은 「J 를 포함하는가」만 본다
        if ((S & (1 << 0)) != 0) dp[1][S] = 1;
    } else {
        // 둘째 날부터는 이전 열과의 인접을 본다
        for (int T = 0; T < 8; T++) {
            if ((S & T) != 0) dp[d + 1][S] += dp[d][T];
        }
    }
}

4. 손으로 표를 채워 본다

서적과 AtCoder가 함께 제시하는 예제 입력을 그대로 쓰겠습니다.

2          ← N = 2 (이틀)
OI         ← 0일차 책임자는 O군, 1일차 책임자는 I군

정답은 7입니다. 표를 채워 봅시다. 열은 8가지 상태 전부이고, 괄호 안은 그 정수가 나타내는 집합입니다.

답은 마지막 행의 합, $1 + 2 + 2 + 2 = \mathbf{7}$입니다.

몇 칸만 소리 내어 읽어 봅시다

• $d=1$행에서 $S = 2\,(\{$O$\})$가 0인 이유 — 0일차 책임자가 O군이니 이 상태는 책임자 조건은 통과합니다. 그런데 갱신원은 $dp[0]$의 $T = 1\,(\{$J$\})$ 하나뿐이고, $2 \mathbin{\&} 1 = 0$입니다. O군 혼자 나오면 J군에게서 열쇠를 받을 방법이 없습니다.
• $S = 3\,(\{$J,O$\})$가 1인 이유 — $3 \mathbin{\&} 1 = 1 \neq 0$이므로 $dp[0][1] = 1$이 흘러들어옵니다. J군이 열쇠를 들고 나오고, 책임자 O군도 함께 나온 스케줄입니다.
• $d=2$행에서 $S = 5\,(\{$J,I$\})$가 2인 이유 — $T$ 중 $5 \mathbin{\&} T \neq 0$인 것을 전부 모으면 $dp[1][3] = 1$과 $dp[1][7] = 1$이 걸립니다. 합쳐서 2입니다.
• $S = 4\,(\{$I$\})$가 1인 이유 — $4 \mathbin{\&} 3 = 0$이라 $dp[1][3]$은 흘러들어오지 못하고, $4 \mathbin{\&} 7 = 4 \neq 0$인 $dp[1][7] = 1$만 남습니다. 1일차에 I군 혼자 나오려면 0일차에 I군도 나와 있어야 한다는 뜻입니다.

5. 답 7을 손으로 세어 본다

$N = 2$는 전탐색이 가능한 크기입니다. 각 날의 상태가 8가지이므로 $8 \times 8 = 64$가지를 전부 확인할 수 있습니다. DP를 믿기 전에 직접 세어 봅시다.

0일차는 책임자 O군을 포함해야 하고(O $\in A_0$), 가상 $-1$열 때문에 J군도 포함해야 합니다(J $\in A_0$). 따라서 $A_0$은 $\{$J,O$\}$ 또는 $\{$J,O,I$\}$의 2가지뿐입니다. 1일차는 책임자 I군을 포함해야 하므로 $A_1$은 $\{$I$\}$, $\{$J,I$\}$, $\{$O,I$\}$, $\{$J,O,I$\}$의 4가지입니다. 여기에 $A_0 \cap A_1 \neq \emptyset$을 걸면,

7가지입니다. 탈락한 유일한 조합은 $A_0 = \{$J,O$\}$, $A_1 = \{$I$\}$ — 교집합이 비어 열쇠를 넘길 수 없는 경우입니다.

이제 이 목록을 4절의 마지막 행과 대조하면, dp[2][S]가 정확히 무엇을 세고 있었는지 드러납니다.

6. 비트 연산으로 집합을 다루기

집합을 정수로 바꾸는 이유는 하나입니다. 배열의 첨자로 쓸 수 있기 때문입니다. Set<Character>는 dp[d][?]의 물음표 자리에 들어갈 수 없지만, 정수 0~7은 들어갑니다. 그 대가로 집합 연산을 비트 연산으로 다시 배워야 합니다.

두 번째 줄이 이 문제의 심장입니다. S & T는 양쪽 모두에서 1인 자리만 살아남는 연산이므로, 그 결과가 0이 아니라는 것은 양쪽에 공통으로 들어 있는 부원이 최소 한 명 있다는 뜻입니다. 1절에서 유도한 $A_{d-1} \cap A_d \neq \emptyset$이 기계어 한 줄로 내려온 것입니다.

if (S & T != 0)          // (X) S & (T != 0) 으로 파싱된다 → 컴파일 에러
if ((S & T) != 0)        // (O)

책임자 조건은 어느 루프에서 거르는가

본편의 코드는 $S$ 루프에 진입하자마자 책임자 조건을 거릅니다.

// J → bit 0, O → bit 1, I → bit 2
int need = 1 << "JOI".indexOf(responsible.charAt(d));

for (int S = 0; S < 8; S++) {
    // d 열은 그날의 책임자를 반드시 포함해야 한다 — 여기서 거른다
    if ((S & need) == 0) continue;

    for (int T = 0; T < 8; T++) {
        if ((S & T) != 0) {
            dp[d + 1][S] = (dp[d + 1][S] + dp[d][T]) % MOD;
        }
    }
}

이것을 안쪽 $T$ 루프로 가져가면 어떻게 될까요? 어느 쪽으로 해도 틀립니다. $S$는 지금 칠하려는 $d$열이고 $T$는 이미 칠해진 $d-1$열입니다. $T$가 만족해야 할 책임자는 $S_d$가 아니라 $S_{d-1}$이며, 그 조건은 이전 단계에서 이미 걸러졌습니다.

다만 어떻게 틀리는지는 두 갈래로 갈립니다. $N \leq 7$의 책임자 배열 3,279가지를 전부 돌려 보면 이렇습니다.

다시 거는 쪽은 전이가 줄어들기만 하므로 답이 결코 커지지 않습니다. 반면 옮기는 쪽은 $S$의 제약이 사라져 오히려 커질 수 있습니다. $S = $ "JJ"가 그런 경우로, 정답 16이 23이 됩니다.

일반화하면 이렇습니다. 새로 정하는 것에만 새 제약을 건다. 이미 확정된 과거에는 그 시점의 제약이 이미 적용되어 있습니다.

7. 확장 — 부원이 $K$명이라면 어디서 터지는가

부원이 3명이라 상태가 8가지였고, 갱신 한 번이 $8 \times 8 = 64$회였습니다. 그래서 전체가 $O(N)$으로 끝났습니다. 그런데 이 $64$는 $4^K$의 $K = 3$인 경우입니다. 부원이 $K$명이면 계산량은 $O(4^K N)$이 됩니다.

($N = 1000$ 기준입니다.) $K = 10$쯤에서 이미 나이브는 버겁습니다. 어디를 줄일 수 있을까요?

범인은 안쪽의 $T$ 루프입니다. "$S$와 만나는 $T$를 전부 더한다"를 매번 $2^K$번 도는 것이 낭비입니다. 여기서 여집합을 쓰는 상투적인 손놀림이 나옵니다. 세기 어려운 것을 세는 대신, 전체에서 세기 쉬운 반대쪽을 뺍니다.

$$\sum_{T \,:\, S \cap T \neq \emptyset} dp[d][T] \;=\; \underbrace{\sum_{T} dp[d][T]}_{\text{전체 합}} \;-\; \underbrace{\sum_{T \,:\, S \cap T = \emptyset} dp[d][T]}_{\text{서로소인 것들의 합}}$$

그리고 "$S$와 서로소"는 "$S$의 여집합의 부분집합"과 같은 말입니다. 즉 뒷항은 부분집합 합입니다.

sub[X] ← X 의 부분집합인 모든 T 에 대한 dp[d][T] 의 합

이 배열은 제타 변환(SOS DP)으로 $O(2^K K)$에 한 번에 구할 수 있습니다. 각 비트에 대해 한 번씩 훑는 것이 전부입니다.

final int FULL = 1 << K;

// 전체 합
int total = 0;
for (int T = 0; T < FULL; T++) total = (total + dp[T]) % MOD;

// sub[X] = X 의 부분집합인 T 들의 dp 합 (제타 변환)
int[] sub = dp.clone();
for (int k = 0; k < K; k++) {
    for (int X = 0; X < FULL; X++) {
        if ((X >> k & 1) != 0) {
            sub[X] = (sub[X] + sub[X ^ (1 << k)]) % MOD;
        }
    }
}

int[] next = new int[FULL];
for (int S = 0; S < FULL; S++) {
    if ((S & need) == 0) continue;          // 그날의 책임자
    int disjoint = sub[(FULL - 1) ^ S];     // S 의 여집합의 부분집합들
    // 뺄셈이므로 음수가 될 수 있다 — MOD 를 한 번 더해 준다
    next[S] = ((total - disjoint) % MOD + MOD) % MOD;
}

이제 하루당 비용이 $O(2^K K)$가 되어, 전체는 $O(2^K K N)$입니다. $K = 10$, $N = 1000$이면 약 $10^7$ — 충분히 들어옵니다.

8. 자주 틀리는 지점 5선

9. 연습 문제

"집합을 통째로 첨자에 넣는" 사고방식이 통하는 문제들입니다. 아래로 갈수록 집합을 다루는 기교가 늘어납니다.

정리

• 복잡한 규칙은 동치인 단순한 조건으로 바꿔 말하는 것이 절반입니다. "열쇠를 누가 가지고 있는가"라는 추적 문제가 $A_{d-1} \cap A_d \neq \emptyset$이라는 한 줄이 되는 순간, 추적할 상태가 사라집니다.
• 첫 항만 규칙이 다르면 가상의 0번째 항으로 흡수할 수 있는지 보세요. dp[0][1 << 0] = 1은 특수 규칙 하나를 초기값 한 줄로 접은 것입니다.
• 최적화 DP는 max, 세는 DP는 sum입니다. 표의 모양이 같아도 마지막 첨자의 의미가 다릅니다 — 경쟁하는 후보인지, 겹치지 않는 분류인지.
• 집합을 정수로 바꾸는 이유는 배열 첨자로 쓰기 위해서이고, 그 대가는 연산자 우선순위 같은 잔가시입니다. (S & T) != 0의 괄호를 잊지 마세요.
• $O(N)$처럼 보이는 계산량 안에 숨은 상수 $4^K$가 있을 수 있습니다. 그 항이 어디인지 알아 두면, 제약이 커졌을 때 어디를 고쳐야 하는지도 압니다.

참고 자료

• 본편: [PAST] Part 2 — 동적 계획법 심화 ①
• 앞선 보충편: Part 2 보충 — AtCounter 문제 풀이
• 1편: Part 2 보충 — 배낭 문제 풀이
• 서적: 「アルゴリズム実技検定 公式テキスト ［上級］～［エキスパート］編」 (マイナビ出版, 2023) — 제2장 2.2절, 예제 2-2-2
• 소스코드: tsutaj/pastbook-2-source-code (Github)
• 일본정보올림픽: https://www.ioi-jp.org/joi/
• AtCoder 공식 사이트: https://atcoder.jp