제출 #134253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134253		imyujin	괄호 문자열 (CEOI16_match)	C++14	10 / 100	207 ms	504 KiB

match

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

char s[MAXN];
bool dp[MAXN][MAXN];
char ans[MAXN];

void solve(int l, int r) {
	if(l > r) return;
	for(int i = r; ; i--) if(s[l] == s[i] && dp[l + 1][i - 1] && dp[i + 1][r]) {
		ans[l] = '(';
		ans[i] = ')';
		solve(l + 1, i - 1);
		solve(i + 1, r);
		return;
	}
}

int main() {
	int N;

	cin >> s;

	for(N = 0; s[N]; N++);
	for(int i = 0; i < N; i++) dp[i + 1][i] = true;
	for(int i = 2; i <= N; i++) for(int j = 0; i + j - 1 < N; j++) {
		for(int k = j + 1; k <= i + j - 1; k++) if(s[j] == s[k] && dp[j + 1][k - 1] && dp[k + 1][i + j - 1]) 
			dp[j][i + j - 1] = true;
	}

	if(!dp[0][N - 1]) cout << -1;
	else {
		solve(0, N - 1);
		for(int i = 0; i < N; i++) cout << ans[i];
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63