[BOJ] 13906 대문자 (C++)
문제 요약
길이 1,000 이하 소문자 문자열이 있다. 여기서 원하는 만큼 지우고 인접한 3개의 같은 소문자를 대문자 1개로 바꾼다. 이렇게 만든 대문자 문자열(소문자 있으면 안됨)의 서로 다른 개수를 구하여라. mod=1,000,000,007.
생각의 흐름
딱봐도 dp. N이 작네 O(N^2) 인가보다. 중복처리 어케하지. aabbba 같은 경우 어케하지. 떨어져 있거나 붙어있거나 상관없이 3개 모이는 게 트리거네. aaabbbaaa 같이 뒤 aaa같은 건 앞 aaa에서도 카운팅 할 수 있네. 3개 모일 때만 하면 됨. 6개 9개 모이거나 하는건 이미 전에 처리했을거니까. 3개 딱 완성했을때 dp[ i ] += dp[ j + 1 ] + 1 에 모듈러 연산. (나 + 이전까지 경우) + (나 하나)
| S | a | a | a | b | b | c | c | c | a | a | b | b | b | a | |
| DP | 10 | 6 | 6 | 5 | 5 | 5 | 2 | 2 | 2 | 1 | 1 | 0 | 0 | 0 | 0 |
풀이
dp인지는 바로 알았다. 하지만 점화식 세우는 게 까다로웠다.
중복처리를 잘 하는 게 관건이었다.
$dp[i] \mathrel{+}= dp[j+1] + 1 \pmod{10^9+7}$
$dp[i]$는 $i$번째부터 시작하는 접미사에서 만들 수 있는 경우의 수. $dp[j+1]$는 $j$ 이후에 경우의 수 모음이다.
그 뜻은 "첫 대문자($j$로 끝나는 알파벳 묶음)에 따라올 뒤에 올 경우들(이후 대문자 경우의 수)"이다. 거기에 대문자 하나 경우의 수 1을 더한다.
$j$가 $i$부터 $N-1$까지 순회하면서 알파벳 별로 최초로 3번째가 될 때 위 식으로 전이한다. 알파벳 별로 딱 3번째에만 전이하므로 aaaa같이 애매한 경우에도 중복이 없다.
시간복잡도는 $N$(문자열 길이)까지 도는 $i$, $j$ 두 for문으로 $O(N^{2})$
제출 코드
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int main() {
cin.tie(0)->sync_with_stdio(0);
string s; cin>>s;
int dp[1001]={0};
for(int i=s.size()-1;i--;) {
int cnt[26]={0};
for(int j=i;j<s.size();j++) if(++cnt[s[j]-'a']==3) dp[i]=(dp[i]+dp[j+1]+1)%MOD;
}
cout<<dp[0];
}