[PAST] Part 2 보충 — AtCounter 문제 풀이

이 글을 쓰는 이유

이 문제는 본편에서 유일하게 손 추적 표가 실린 예제입니다. 다만 그 표는 목표 문자열을 "atc"로 줄이고 $S = $ "aatctc"로 둔 축소판이었습니다. 감을 잡는 데는 충분하지만, 진짜 문제를 풀 때 걸려 넘어지는 곳은 따로 있습니다.

• 서적과 AtCoder가 제시하는 진짜 예제는 $S = $ "attcordeer"이고 답은 4입니다. 그런데 각 글자의 등장 횟수를 곱하면 $1 \times 2 \times 1 \times 1 \times 1 \times 2 \times 2 = 8$입니다. 어디서 절반이 사라졌을까요?
• 2차원 점화식은 "뽑는다 / 뽑지 않는다" 두 갈래였는데, 본편의 1차원 코드에는 갱신이 하나뿐입니다. "뽑지 않는 경우"는 어디로 갔을까요?
• 본편은 "$j$를 역순으로 돌아야 한다"고 강조했습니다. 그런데 이 문제는 정순으로 돌려도 정답이 나옵니다. 왜일까요? 그리고 언제부터 역순이 진짜로 필요해질까요?
• $N \leq 10^6$은 실제로 무엇을 금지하고 있을까요?

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

1. 문제를 다시 읽는다 — 제약이 설계를 결정한다

길이 $N$의 문자열 $S$가 주어집니다. $S$에서 몇 글자를 뽑아내는 방법은 $2^N$가지인데, 그중 뽑아낸 글자를 원래 순서대로 나열했을 때 "atcoder"가 되는 것이 몇 가지인지를 $10^9 + 7$로 나눈 나머지로 구합니다.

1편에서와 같이, 제약부터 읽습니다.

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

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

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

• 초기 조건 — dp[0][0] = 1 (아무것도 뽑지 않으면 빈 문자열 하나)
• $S_i$를 뽑지 않는다 — $dp[i+1][j] \mathrel{+}= dp[i][j]$
• $S_i$를 뽑는다 — $S_i = T_{j-1}$일 때만 $dp[i+1][j] \mathrel{+}= dp[i][j-1]$
• 답 — dp[N][7] 한 칸
• 계산량 — $O(7N)$

3. 진짜 예제를 끝까지 따라가 본다

본편의 축소판 대신, 서적과 AtCoder가 제시하는 실제 예제로 표를 채웁니다.

10
attcordeer     ← 답은 4

행은 "지금까지 본 글자 수 $i$", 열은 ""atcoder"의 몇 번째까지 맞췄는가 $j$"입니다.

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

• $j = 0$ 열이 끝까지 1 — "아무것도 안 뽑고 빈 문자열을 만드는 방법"은 언제나 딱 하나입니다. 이 열은 갱신 대상이 아니라 모든 것이 흘러나오는 원천입니다.
• $i = 3$에서 $dp[3][2]$가 2로 뛴다 — 3번째 글자가 두 번째 t입니다. 여기서 $dp[2][1] = 1$이 더해져 $1 + 1 = 2$가 됩니다. "a 뒤에 t를 붙이는 방법이 2번째 t를 쓰는 것과 3번째 t를 쓰는 것, 두 가지"라는 뜻입니다.
• $i = 9$에서 $dp[9][6]$이 4로 뛴다 — 두 번째 e입니다. 마찬가지로 $dp[8][5] = 2$가 더해져 $2 + 2 = 4$가 됩니다. t의 2가지와 e의 2가지가 곱해져 4가 된 순간입니다.

4. 답이 4인 이유 — 곱셈은 왜 틀리는가

가장 먼저 떠오르는 생각은 아마 이럴 겁니다. ""atcoder"의 각 글자가 $S$에 몇 번 나오는지 세서 곱하면 되는 것 아닌가?"

곱하면 $1 \times 2 \times 1 \times 1 \times 1 \times 2 \times 2 = \mathbf{8}$입니다. 그런데 정답은 4입니다. 정확히 절반입니다.

범인은 r입니다. r은 6번째와 10번째에 있지만, "atcoder"에서 r은 맨 마지막 글자입니다. 즉 d(7번째)와 e(8 또는 9번째)보다 뒤에 있어야 합니다. 6번째 r은 d보다 앞이라 쓸 수가 없습니다. 곱셈은 이 순서 조건을 전혀 모릅니다.

실제로 조건을 만족하는 조합은 정확히 이 4가지입니다.

자유도는 t의 2가지와 e의 2가지뿐이고, r은 10번째로 고정됩니다. $2 \times 2 = 4$입니다.

5. 1차원으로 접기 — "뽑지 않는 경우"는 어디로 갔는가

본편의 Java 코드를 다시 봅시다. 2차원 점화식은 갈래가 둘이었는데, 여기엔 갱신이 하나뿐입니다.

long[] dp = new long[M + 1];
dp[0] = 1;

for (int i = 0; i < N; i++) {
    char c = S.charAt(i);
    for (int j = M; j >= 1; j--) {
        if (c == T.charAt(j - 1)) {
            dp[j] = (dp[j] + dp[j - 1]) % MOD;   // 「뽑는다」 밖에 없다
        }
    }
}

"뽑지 않는 경우"인 $dp[i+1][j] \mathrel{+}= dp[i][j]$는 사라진 것이 아니라 공짜가 된 것입니다.

2차원에서는 $i$행과 $i+1$행이 다른 메모리였기 때문에, "안 뽑았다"는 사실도 값을 복사해서 표현해야 했습니다. 1차원에서는 행이 하나뿐이라 아무것도 하지 않으면 값이 그대로 남습니다. 그 "그대로 남음"이 곧 "안 뽑음"입니다.

덕분에 "atcoder"에 없는 글자 — "attcordeer"에는 없지만, 가령 z — 를 만나면 안쪽 루프가 일곱 번 비교만 하고 아무것도 쓰지 않은 채 지나갑니다. 3절에서 본 "6행 = 5행"도 같은 현상의 부분적인 모습입니다.

6. 역순은 정말 필요한가

본편은 $j$를 역순으로 도는 것을 강조하며, 1편의 1차원 배낭과 "완전히 같은 이유"라고 했습니다. 오름차순이면 dp[j-1]이 이미 이번 글자를 소비한 값이 되어 한 글자를 두 번 쓰는 셈이 된다는 것입니다.

설명은 정확합니다. 그런데 실제로 정순으로 바꿔서 제출하면 어떻게 될까요?

그렇다면 역순은 불필요한 미신일까요? 아닙니다. 목표 문자열을 "aa"로 바꿔 보면 즉시 드러납니다.

$S = $ "aa"에서 "aa"가 되는 부분수열은 1가지뿐인데 정순은 3을 내놓습니다. 같은 글자를 두 번 세었기 때문입니다. 중복 글자가 있는 목표 문자열로 무작위 실험을 2,000회 돌렸을 때 정순은 1,046회 틀렸고, 역순은 0회 틀렸습니다.

7. $N \leq 10^6$이 요구하는 것

1편의 배낭은 $N \leq 100$이라 무엇을 해도 여유로웠습니다. 여기는 $N$이 1만 배입니다. 제약이 실제로 무엇을 금지하는지 봅시다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine().trim());
char[] s = br.readLine().trim().toCharArray();   // charAt 을 100만 번 부르지 않는다

final int MOD = 1_000_000_007;
final char[] t = "atcoder".toCharArray();

long[] dp = new long[t.length + 1];
dp[0] = 1;

for (char c : s) {
    for (int j = t.length; j >= 1; j--) {
        if (c == t[j - 1]) {
            dp[j] = (dp[j] + dp[j - 1]) % MOD;
        }
    }
}
System.out.println(dp[t.length]);

8. 자주 틀리는 지점 5선

9. 연습 문제

"문자열을 앞에서부터 훑으며 진행 상태를 첨자로 들고 가는" 사고방식이 통하는 문제들입니다.

정리

• 곱셈은 순서를 모릅니다. 등장 횟수를 곱해 8이 나왔지만 답은 4였고, 차이는 "쓸 수 없는 위치의 r" 하나였습니다. DP가 이기는 것은 표를 한 방향으로만 훑는 구조에 순서 조건이 흡수되어 있기 때문입니다.
• 1차원 롤링에서 "아무것도 하지 않음"은 그 자체로 하나의 갱신입니다. 2차원의 두 갈래 중 하나가 공짜가 되는 것이 롤링의 이득입니다.
• 우연히 맞는 코드를 경계하세요. 정순 갱신이 이 문제에서 통과하는 것은 "atcoder"의 일곱 글자가 전부 다르기 때문이지, 알고리즘이 옳기 때문이 아닙니다. 목표 문자열에 중복이 하나만 생겨도 절반 이상의 경우에서 틀립니다.
• int도 7%의 여유로 들어가지만, 그 여유를 믿는 것 역시 같은 종류의 도박입니다.
• $N$이 $10^6$이면 알고리즘만큼 입출력이 중요합니다. TLE가 났을 때 DP를 먼저 의심하지 마세요.

참고 자료

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