[BOJ] 백준 10422. 괄호 (Gold IV)

오랜만에 가벼운 문제로 백준 포스팅을 들고와보았다~!

문제는 아래와 같다.

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

10422번: 괄호

괄호 관련 문제는 언제나 재밌다

재미는 개뿔...ㅠㅠ

---

의식의 흐름 및 해설

1. O(N^2) dp

괄호를 보면 보통 나는 stack을 떠올리는데, 이 문제는 경우의 수를 묻기 때문에 바로 dp를 떠올릴 수 있었다.

괄호 개수에 따라 충분히 메모이제이션이 가능하다는 사실은 한눈에 보이기 때문.

 

일단 N이 상당히 작은 데다가, 짝수만 주어지기 때문에 O(N^2) 풀이가 가능하다.

왼쪽 괄호보다 오른쪽 괄호가 더 많이 나오는 순간, 무조건 그 문자열은 올바른 괄호문자열이 아니라는 사실을 이용하자!

 

그렇게 해서 왼쪽 괄호 개수와 오른쪽 괄호 개수가 같으면 1을 더해주면 된다.

ll dp(ll left, ll right) {
	if (left < 0 || right < 0)return 0;
	if (left + right == 0)
		return !left && !right ? 1 : 0;
	ll& ret = d[left][right];
	if (~ret)return ret;
	ret = 0;
	ret += dp(left - 1, right);
	ret %= MOD;
	if (left < right) {
		ret += dp(left, right - 1);
		ret %= MOD;
	}
	return ret % MOD;
}

 

2. 카탈란 수 이용하기

그런데, 사실 이 문제는 Well-Known에 해당하는 카탈란 수를 이용하면 된다 :)

카탈란 수 정의는 구글링하면 굉장히 잘 나오기 때문에 생략한다.

아예 카탈란 수 정의 자체를 알고 있는지 묻는 문제이며, 이는 O(N)에 해결할 수 있다.

for (int i = 4; i < MAX; i++) {
    for (int j = 0; j < i; j++) {
        d[i] += d[j] * d[i - j - 1];
        d[i] %= MOD;
    }
}

---

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 5011;
const int MOD = 1e9 + 7;
ll N, d[MAX] = { 1,1,2,5 };
int main() {
	cin.tie(0)->sync_with_stdio(0);

	int t;
	cin>>t;
	for (int i = 4; i < MAX; i++) {
		for (int j = 0; j < i; j++) {
			d[i] += d[j] * d[i - j - 1];
			d[i] %= MOD;
		}
	}
	while(t--){
		cin >> N;
		if(N%2){
			cout<<0<<"\n";
			continue;
		}
		N/=2;
		cout << d[N] << "\n";	
	}
}

---

G2~G3 투표도 되게 많던데,

나도 카탈란 수 문제였다면 이에 동의하나, 이 문제는 O(N^2) dp로도 풀리기 때문에 위와 같이 투표하였다.

 

오랜만에 재밌는 문제를 만난 듯하다.

시간 남으면 플레티넘 문제들도 다시 오래 고민해보고 풀어보는 시간을 가져봐야겠다 ㅎㅎ