BOJ 13906 - 대문자
P3…G2 태그 걸고 난이도 가리고 풀고있었는데 플레 3 등장
DP인건 쉽게 알 수 있었는데 어떤식으로 점화식을 세울지 까다로운 문제였다.
내 풀이
$dp[i]=i$ 부터 $s_i$ 로 시작해서 한 개 이상의 $s_i$ 대문자인 문자를 만들고 $s$의 끝까지 구성해나갈 때의 경우의 수
라고 하자. $O(n^2)$에 풀 수 있다.
점화식이 단순한만큼 transition이 까다롭다. 중복되는 경우를 제거함이 핵심이다.
일단 점화식 말고 정답 구성을 살펴보면,
어떤 $i=0$ 부터 보면서 $s_i$ 문자가 한 번도 안쓰였을 때만 정답에 더해준다.
왜냐면 어떤 문자 $c$가 이미 정답에 더해졌다고 하자.
$aaabbcccaaa$ 라는 문자가 있을 때 제일 앞에 나오는 $a$ 부분의 정답을 구해주었는데,
어차피 여기서 호출하는 DP함수 내부에서 뒤에 있는 $a$에서 시작하는 경우까지 세주기 때문에 같은 문자에 대해 한 번만 정답에 바깥에선 더해주면 된다.
int ans = 0;
vi used(26);
for (int i = 0; i < n;) {
int j = i;
if (!used[s[i] - 'a']) {
debug(i, fn(i));
used[s[i] - 'a'] = 1;
ans = md(ans + fn(i));
}
while (j < n && s[i] == s[j])j++;
i = j;
}
cout << ans;
이제 점화식을 보자.
현재 $dp[i]$ 를 구하고 있으면 $j \coloneqq i \to \vert s \vert$ 까지 순회한다.
만약 $s_i=s_j$ 라면 현재 $s_i$의 개수라는 뜻으로 $cnt \coloneqq cnt+1$ 을 해준다.
이제 $last_c$ 를 $c$라는 $s_i \neq c$ 라는 문자가 $j$에서 등장할 때마다 $cnt$ 의 값이였다고 하자.
$dp[j] \cdot (\left\lfloor \dfrac{cnt}{3} \right\rfloor-last_c)$ 를 정답에 더해주어야 한다.
이는 앞서 말했듯이 중복을 세주지않기 위함인데, $a$가 $3$개 등장하고 $b$가 등장하나, $a$가 $4$개 등장하고 $b$가 등장하나 동일하기 때문이다.
따라서 현재 $s_i$ 로 대문자를 몇개를 만들지를 고정하고 해당 대문자 개수를 만들 수 있게 된 이후 시점에 나오는 $s_i \neq c$ 인 다른 문자들에 대해서 새롭게 $s_i$ 대문자를 만들 수 있는 개수만큼 $dp[j]$에 곱해주는 것이다.
또한 $j$ 반복문을 모두 순회한 후엔 정답에 $\left\lfloor \dfrac{cnt}{3} \right\rfloor$ 을 더해주면 된다. 다른 문자열을 안붙이고 $s_i$ 를 이용해서 끝까지 간 경우도 더해주는 것이다.
const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
int fac[1001], dp[1001];
void solve() {
memset(dp, -1, sizeof dp);
fac[0] = 1;
for (int i = 1; i <= 1000; i++) fac[i] = md(fac[i - 1] * i);
string s;
cin >> s;
int n = sz(s);
function<int(int)> fn = [&](int i) -> int {
int &ret = dp[i];
if (~ret) return ret;
int cnt = 0;
ret = 0;
vi last(26);
for (int j = i; j < n; j++) {
if (s[j] == s[i]) cnt++;
else {
ret = md(ret + fn(j) * (cnt / 3 - last[s[j] - 'a']));
last[s[j] - 'a'] = cnt / 3;
}
}
ret = md(ret + (cnt / 3));
return ret;
};
int ans = 0;
vi used(26);
for (int i = 0; i < n;) {
int j = i;
if (!used[s[i] - 'a']) {
debug(i, fn(i));
used[s[i] - 'a'] = 1;
ans = md(ans + fn(i));
}
while (j < n && s[i] == s[j])j++;
i = j;
}
// A, AA, AB, AC, ACA, ACB,
cout << ans;
}
다른 풀이
채점 현황에 다른 풀이를 하나 가져왔고 공부해보자.
아래 코드 기준으로 설명한다.
$D[i]=i$ 부터 시작하는 문자열에서 $s$의 끝까지 진행하며 구성했을 때 서로 다른 대문자 문자열 개수
라고 한다.
$j \coloneqq i \to \vert s \vert-1$ (0-index) 까지 순회하며 나오는 문자들의 개수를 세준다.
어떤 문자가 정확히 $3$개가 될 때마다 $D[j+1]$ 도 더해주고(새로 생긴 대문자 하나를 붙이고 $D[j+1]$ 의 것들도 그 뒤에 concat한 것) 새로 생긴 대문자 하나만 사용한 문자만 쓰는 걸 의미하는 $+1$ 도 해준다.
//https://www.acmicpc.net/source/9079554
#include<cstdio>
#include<cstring>
const int MOD = 1e9 + 7;
char s[1005];
int D[1005], cnt[26];
int main(){
scanf("%s",s);
int n = strlen(s);
for (int i = n - 1; i >= 0; i--){
memset(cnt, 0, sizeof(cnt));
for (int j = i; j < n; j++){
cnt[s[j] - 'a']++;
if (cnt[s[j] - 'a'] == 3){
D[i] = (D[i] + D[j + 1] + 1) % MOD;
}
}
}
printf("%d",D[0]);
return 0;
}
Comments