백준 BOJ 17623 - 괄호

정올문제의 연속.

일단 디피를 짜는것까지는 좀 빨라진거같아 다행이다.

 

괄호 문자열은 더하거나 아니면 감싸주는 방식으로 만들 수 있는데,

이는 디피의 특성인 작은 정답이 모여 큰 정답을 만들 수 있다는것과 같다.

문자열을 K로 두고

string dp[i]를 val(K) = i인 문자열 중 dmap(K)의 최소값을 저장한다.

여기서 dmap(K)가 롱롱인트범위를 벗어날 수도 있을거같다는 생각에 혹시몰라서

문자열형으로 만들어줬고,

그렇기때문에 문자열 두개를 비교하는 string cmp함수를 만들었다

문자열을 숫자로 볼때 더 작은 값을 가지는 문자열을 반환해준다.

 

string convert(string s)는 dp배열에서 저장하는 값이 dmap()일때, 

이 dmap()의 반환값 형식으로 저장된 값을 다시 괄호 문자열로 변경해주는 함수이다.

간단하게 작성할 수 있다.

 

string dp[i]를 채우는 과정에서,

i = a+b( a와 b는 임의의 자연수 ) 가 될 수 있으므로,

기존에 만든 dp배열에서 값들을 확인해가며 저 a와 b에 해당하는 값을 찾아주어야 한다.

 

dp[i] = cmp(dp[i], dp[j]+dp[i-j]) 을 통해 일일히 확인해 볼 수 있다.

 

또한 문자열을 감싸는 과정에서 나누어지는지를 한번 더 확인해줄 수 있고,

이렇게 dp[i]를 O(N^2) 에 채워줄 수 있다.

출력은 단순히 dp[n]을 convert함수에 넣어주기만 하면 된다.

깔끔하게 AC.

 

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

string cmp(string a, string b,int ptr){
	if(a=="") return b;
	if(b=="") return a;
	if(a.length() != b.length()) return a.length()>b.length()?b:a;
	if(ptr>a.length())           return a;
	if(a[ptr] != b[ptr])         return a[ptr]>b[ptr]?b:a;
	
	return cmp(a, b, ptr+1);
}

string convert(string s){
	string ans;
	for(int i=0; i<s.length(); i++){
		if(s[i]=='1') ans+='(';
		if(s[i]=='2') ans+=')';
		if(s[i]=='3') ans+='{';
		if(s[i]=='4') ans+='}';
		if(s[i]=='5') ans+='[';
		if(s[i]=='6') ans+=']';
	}
	return ans;
}

string dp[12345];

int main(){
	dp[1] = "12";
	dp[2] = "34";
	dp[3] = "56";
	
	//string a,b;
	//cin >> a;
	//cout << cmp(a,b,0);
	
	for(int i=4; i<=1000; i++){
		dp[i] = (string)"1"+"2"+dp[i-1];
		for(int j=2; j<i; j++) dp[i] = cmp(dp[i], dp[j]+dp[i-j], 0);
		if(i%2 == 0) dp[i] = cmp(dp[i], "1"+dp[i/2]+"2", 0);
		if(i%3 == 0) dp[i] = cmp(dp[i], "3"+dp[i/3]+"4", 0);
		if(i%5 == 0) dp[i] = cmp(dp[i], "5"+dp[i/5]+"6", 0);
	}
	
	int t,n;
	cin >> t;
	while(t--){
		cin >> n;
		cout << convert(dp[n])<< "\n";
	}
	return 0;
}