[BOJ 3012 // C++] 올바른 괄호 문자열

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

 

이번에 볼 문제는 백준 3012번 문제인 올바른 괄호 문자열이다.
문제는 아래 링크를 확인하자.

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

3012번: 올바른 괄호 문자열

일단 이 문제는 주어진 문자열의 '?'을 적절히 바꿔 올바른 괄호 문자열로 만들 수 있는 경우의 수를 세는 문제이다. 다만, 출력 방식이 많이 까다로워 주의해야 한다. 문제를 먼저 해결해보자.

 

일단 s의 자릿수가 홀수라면 당연히 답은 0일 것이다. 아래는 s의 자릿수가 짝수인 경우를 다룬다.

 

dp[L][R]을 문자열의 L번째 문자부터 R번째 문자까지로 이루어진 부분문자열을 올바른 괄호 문자열로 만들 수 있는 경우의 수로 정의하자. 이러한 모든 올바른 괄호문자열은 [L,R]에 포함되는 정수 i 대하여 처음으로 [L,i]가 올바른 괄호문자열이 되는 최소 정수 i가 존재한다. 이를 이용해 점화식을 세워 문제를 해결할 수 있다.

 

다음으로, 출력조건을 유심히 살펴보자. 이 문제는 답이 5자리를 넘을 경우 하위 5자리만을 남겨 출력할 것을 요구하고 있다. 즉, 답이 5자리 이내라면 leading zero 없는 답을 출력해야하고, 5자리보다 많다면 100000으로 나눈 나머지를 leading zero를 포함하여 출력해야 하는 것이다.

 

이를 구현하기 위해, 글쓴이는 각 결과가 10만 이상의 값이 된 적이 있는지의 여부와 0 값이 10만 이상의 값을 10만으로 나눈 값인지 아니면 정말 0인지 등을 관리하였다.

 

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

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int slen;
string s;
ll dp[200][200];
bool visited[200][200];
bool overflowed[200][200];
bool zero[200][200];

bool chk(int L, int R) {
	return (s[L] == '(' && s[R] == ')')
		|| (s[L] == '{' && s[R] == '}')
		|| (s[L] == '[' && s[R] == ']')
		|| (s[L] == '(' && s[R] == '?')
		|| (s[L] == '{' && s[R] == '?')
		|| (s[L] == '[' && s[R] == '?')
		|| (s[L] == '?' && s[R] == ')')
		|| (s[L] == '?' && s[R] == '}')
		|| (s[L] == '?' && s[R] == ']');
}

ll func(int L, int R) {
	ll& cur = dp[L][R];
	if (visited[L][R]) return cur;
	visited[L][R] = 1;

	if (L > R) return cur = 1;

	for (int idx = L + 1; idx < R; idx += 2) {
		if (chk(L, idx)) {
			cur += func(L + 1, idx - 1) * func(idx + 1, R);
			if (overflowed[L + 1][idx - 1] && !zero[idx + 1][R]) overflowed[L][R] = 1;
			else if (overflowed[idx + 1][R] && !zero[L + 1][idx - 1]) overflowed[L][R] = 1;
		}
		else if (s[L] == '?' && s[idx] == '?') {
			cur += func(L + 1, idx - 1) * func(idx + 1, R) * 3;
			if (overflowed[L + 1][idx - 1] && !zero[idx + 1][R]) overflowed[L][R] = 1;
			else if (overflowed[idx + 1][R] && !zero[L + 1][idx - 1]) overflowed[L][R] = 1;
		}
	}

	int idx = R;
	if (chk(L, idx)) {
		cur += func(L + 1, idx - 1);
		if (overflowed[L + 1][idx - 1]) overflowed[L][R] = 1;
	}
	else if (s[L] == '?' && s[idx] == '?') {
		cur += func(L + 1, idx - 1) * 3;
		if (overflowed[L + 1][idx - 1]) overflowed[L][R] = 1;
	}

	if (cur == 0 && !overflowed[L][R]) zero[L][R] = 1;
	else if (cur > 99999) overflowed[L][R] = 1, cur %= 100000;

	return cur;
}

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

	cin >> slen >> s;

	if (slen & 1) cout << 0;
	else {
		ll ans = func(0, slen - 1);
		if (overflowed[0][slen - 1]) {
			if (ans < 10000) cout << 0;
			if (ans < 1000) cout << 0;
			if (ans < 100) cout << 0;
			if (ans < 10) cout << 0;
		}
		cout << ans;
	}
}