BOJ 10279 부분 수열이 아님

우선, 길이 $m$의 모든 문자열이 $S$의 부분 수열일 조건을 생각해 봅시다.

• 길이 1의 모든 문자열이 $S$의 부분 수열이려면, $S$가 모든 문자를 한 번 이상 포함하면 됩니다.
• 길이 2의 모든 문자열이 $S$의 부분 수열이려면, 모든 문자 중에서 첫 등장이 가장 늦는 문자 $c$를 생각해 봅시다. $c$로 시작하는 길이 2의 모든 문자열이 $S$의 부분 수열이기 위해서는 $c$ 뒤에 모든 문자가 한 번 이상 등장해야 합니다. 그렇다면 $c$보다 첫 등장이 빠른 모든 문자에 대해서도 그 뒤에 모든 문자가 한 번 이상 등장하게 되므로, 길이 2의 모든 문자열이 $S$의 부분 수열이 됩니다.
• 이를 반복하면, $S$의 앞에서부터 모든 문자가 한 번 이상씩 등장하는 서로 겹치지 않는 구간 $m$개를 만들 수 있으면 길이 $m$의 모든 문자열이 $S$의 부분 수열이 되며, 그렇지 않을 경우 $S$의 부분 수열이 아닌 길이 $m$의 문자열이 존재합니다.

이제 문제의 정답이 되는 길이 $m$을 찾았다고 치고, 그러한 문자열의 개수를 구하는 방법을 생각해 봅시다.

DP 테이블을 다음과 같이 정의합니다.

• DP[i][k]: 길이가 k이고 S[:i]의 부분 수열이 아닌 문자열의 개수

그러면 구해야 하는 값은 l = len(S)일 때 DP[l][m]이 됩니다.

이제 $S$에서 맨 앞에서부터 모든 글자를 포함하는 $m-1$개의 구간을 만들고, 남는 마지막 구간에 존재하는 글자와 존재하지 않는 글자를 생각해 봅시다.

• 글자 $c$가 마지막 구간에 존재한다면, $c$로 끝나는 $n^{m-1}$개의 문자열은 모두 $S$의 부분 수열이므로 무시합니다.
• 그렇지 않다면, $c$로 끝나는 문자열 중 $S$의 부분 수열이 아닌 것의 개수는 $c$의 마지막 인덱스가 $i_c$일 때 DP[i_c][m-1]입니다. 구간의 정의에 의해, $i_c$는 $m-1$번째 구간 내에 있습니다. 현재 DP값은 이러한 이전 DP값의 합이 됩니다.

재귀가 $m$을 1 감소시키면서 직전 구간에 포함된 인덱스로 진행되므로, DP[i][k]에서 두 번째 인덱스는 필요 없게 됩니다.

DP 전이가 마지막 구간에 존재하지 않는 모든 글자에 대한 이전 DP값의 합이 되는데, 각 구간 내에서 글자를 하나 추가할 때마다 아직 존재하지 않는 글자가 0개 또는 1개 감소하므로, 이전 DP값으로부터 $\mathcal{O}(1)$에 DP값을 구할 수 있습니다.

새로운 구간에 진입하는 경우에는 $n$개의 DP값을 모두 더해줘야 하는데, 각 구간의 길이가 적어도 $n$이므로 이렇게 더해지는 DP값의 개수의 총합은 $l$을 넘지 않습니다. 따라서 이 부분은 그대로 나이브하게 구현해주면 됩니다.