BOJ 13906 - 대문자

image.png

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;
}

Tags:

Categories:

Updated:

Comments