POJ 1141 Brackets Sequence(구간 DP)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#include <string>
#include <map>
#define INF 1000000
int dp[105][105];
int path[105][105];
char s[105];
bool mat[105][105];

bool match(char a,char b){
	return a=='['&&b==']'||a=='('&&b==')';
}

void print(int a,int b){
	if(a>b) return ;
	if(a==b){
		if(s[a]=='('||s[a]==')') printf("()");
		else printf("[]");
	}

	else if(mat[a][b]){
		printf("%c",s[a]);
		print(a+1,b-1);
		printf("%c",s[b]);
	}
	else {
		print(a,path[a][b]);
		print(path[a][b]+1,b);
	}
}

int main(){
	scanf("%[^
]s",s);
	int len=strlen(s);
	if(len==0){
		printf("
");
	}
	else{
		for(int i=0;i<len;i++){
			dp[i][i]=1;
		}
		for(int i=0;i<len-1;i++){
			if(match(s[i],s[i+1])){
				dp[i][i+1]=0;
				mat[i][i+1]=1;
			}
			else{
				dp[i][i+1]=2;
				path[i][i+1]=i;
			}
		}
		for(int i=3;i<=len;i++){
			for(int j=0;j<len-i+1;j++){

				dp[j][j+i-1]=INF;
				int ist=0;
				for(int k=j;k<j+i-1;k++){
					if(dp[j][k]+dp[k+1][j+i-1]<dp[j][j+i-1]){
						dp[j][j+i-1]=dp[j][k]+dp[k+1][j+i-1];
						ist=k;
					}
				}
				if(match(s[j],s[j+i-1])){
					if(dp[j+1][j+i-2]<dp[j][j+i-1]){
						mat[j][j+i-1]=1;
						dp[j][j+i-1]=dp[j+1][j+i-2];
					}
				}
				path[j][j+i-1]=ist;
			}
		}
		print(0,len-1);
		printf("
");
	}
	return 0;
}