PS/BOJ

[BOJ] 13906 대문자 (C++)

싱깅칭 2026. 11. 21. 19:47

문제 요약

길이 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];
}