[BOJ/백준][Gold2] 17623 : 괄호 (C++)

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

17623번: 괄호

 

 

[난이도] Gold2
[유형] DP

[풀이]
val[i] : val(X) = N을 만족하는 올바른 괄호 문자열 중에서 dmap(X) 값이 최소인 X

val[i]가 될 수 있는 후보 문자열은
괄호를 감싸는 연산으로 만든
"1" + val[i/2] + "2" (소괄호)
"3" + val[i/3] + "4" (중괄호)
"5" + val[i/5] + "6" (대괄호)
와
concatenation 으로 만든
val[i-j]+val[j] (1<= j < i) 가 있습니다.

이들 중 최솟값을 val[i]로 업데이트 해주면 되는데
최솟값을 정수로 비교하려면 정수 범위를 넘어가버려서 비교가 불가합니다..
그러므로 string 상태에서 비교를 해야합니다.
string 숫자 비교시
12221 보다 344가 크다고 판단하기 때문에
우선 숫자 string의 크기부터 비교해주어야 합니다.

 

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int tc,N;
string val[1001],cvt="0(){}[]";
string check(string a,string b){
    if(b=="-1") return a;
    if(a.size() < b.size()) return a;
    if(a.size() > b.size()) return b;
    return min(a,b);
}
void sol(){
    for(int i=1;i<=1000;i++) val[i]="-1";
    val[1]="12";
    val[2]="34";
    val[3]="56";
    for(int i=4;i<=1000;i++){
        string s;
        if(i%2==0) val[i]=check("1"+val[i/2]+"2",val[i]);
        if(i%3==0) val[i]=check("3"+val[i/3]+"4",val[i]);
        if(i%5==0) val[i]=check("5"+val[i/5]+"6",val[i]);
        for(int j=1;j<i;j++) {
            val[i] = check(val[i-j]+val[j],val[i]);
        }
    }
}
int main(){
    cin >> tc;
    sol();
    while(tc--){
        cin >> N;
        for(auto c : val[N]) {
            cout << cvt[c-'0'];
        }
        cout <<'\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/17623.cpp