[BOJ 13906 // C++] 대문자

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13906번 문제인 대문자이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/13906 

13906번: 대문자

dp[i]를 주어진 문자열의 i번째 문자를 마지막 문자로 남겨 생성할 수 있는 대문자 문장의 경우의 수로 정의하자. 위와 같은 문장은 i번째 문자를 대문자로 바꾼 문자로 끝나고, 해당 알파벳을 지우면 (1) 빈 문자열("")이 되거나 (2) 각 대문자 알파벳('A', ..., 'Z')로 끝나는 문자열이 됨을 관찰하자.

 

위의 관찰을 이용해 점화식을 세우고 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#define MOD 1000000007
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;

string s; int slen;
ll dp[1000]; // [i]: i번째 idx로 끝나는 문자열 개수
int visited[128];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	slen = s.length();

	for (int i = 0; i < slen; i++) {
		memset(visited, 0, sizeof(visited));
		char& c = s[i];
		int cnt = 1;
		bool chk = 0;

		for (int j = i - 1; j > -1; j--) {
			if (chk) {
				if (!visited[s[j]]) {
					visited[s[j]] = 1, dp[i] += dp[j];
				}
			}
			else {
				if (s[j] == c) cnt++;
				if (cnt == 3) chk = 1, dp[i] = 1;
			}
		}
		dp[i] %= MOD;
	}

	ll ans = 0;
	memset(visited, 0, sizeof(visited));
	for (int i = slen - 1; i > -1; i--) {
		if (!visited[s[i]]) {
			visited[s[i]] = 1, ans += dp[i];
		}
	}

	cout << ans % MOD;
}