글 읽기 - 괄호 매칭 dp문제... 반례를 알려주세요!

insu_nym 6년 전 0

빈 문자열은 올바른 괄호 문자열이다.
A가 올바른 괄호 문자열이라면, (A), [A], {A}도 올바른 괄호 문자열이다.
A와 B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열이다.

문제에 주어진 조건대로 DP를 짜서 풀었(다고 생각하)는데요... 몇 가지 테스트케이스를 만들어 봐도 어디서 망쳤는지 못 찾겠습니다 ㅠㅠ.

혹시 눈에 띄는 반례가 있다면 알려주세요! 감사합니다~

#include <iostream>
#include <cstring>
using namespace std;
string str;
int dp[200][200];

int go(int l, int r) {
	if (l >= r) {
		return 0;
	} else if (dp[l][r] != -1) {
		return dp[l][r];
	}

	int& ret = dp[l][r];
	ret = 0;
 	if ((r - l + 1) % 2 == 0) {
 		if ((str[l] == '{' && str[r] == '}')
			|| (str[l] == '[' && str[r] == ']')
			|| (str[l] == '(' && str[r] == ')')
			|| (str[l] == '?' && (str[r] == '}' || str[r] == ']' || str[r] == ')'))
			|| ((str[l] == '{' || str[l] == '[' || str[l] == '(') && str[r] == '?')
			|| (str[l] == '?' && str[r] == '?')) {
 			if (l == r - 1) {
				ret = 1;
			} else {
				ret += go(l + 1, r - 1);

			}
			
			if (str[l] == '?' && str[r] == '?')
				ret *= 3;
 		} 
		
		for (int k = l + 1; k < r - 1; k += 2) {
			ret += go(l, k) * go (k + 1, r);
		}
	} 

	return ret;
}

int main() {
	memset(dp, -1, sizeof(dp));
	int n;
	cin>>n;
	if (n % 2) {
		cout<<0;
		return 0;
	} else if (n == 0) {
		cout<<1;
		return 0;
	}

	cin>>str;
	cout<<go(0, n - 1)<<endl;

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

괄호 매칭 dp문제... 반례를 알려주세요!

insu_nym 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말