KOI 2019 2차 대회 2번 '괄호' 풀이

※복습 : 

문제 :  괄호

문제 링크

 

사용 알고리즘 : 다이나믹 프로그래밍

 

풀이:

2개의 괄호문자열을 대소 비교하는 방법에 주목하자. 

길이가 짧으면 작다. 길이가 같다면 (,),{,},[,] 순으로 작으므로 10진법 수 비교하듯이 하면 된다.

 

즉, DP 테이블 자체를 문자열로 할 수 있다는 뜻이다.

 

dt[N]  : val( str ) = N 인 문자열 str 중 dmap(str) 값이 가장 작은 str

 

이때 dmap은 단순히 문자열의 괄호 문자를 숫자로 치환한 것을 의미한다.

아래 map을 참고하자.

 

이제 문제의 규칙을 이용하여 적당히 DP를 돌려주면 된다. 테스트케이스가 여러개 들어올 수 있으므로 미리 dt를 채우면 된다. 이 문제의 경우 반복문이 간단하다.

 

코드

#include<bits/stdc++.h>
using namespace std;
string dt[1020];
map<char,int> mp={
    {'(',1},
    {')',2},
    {'{',3},
    {'}',4},
    {'[',5},
    {']',6},
};
bool cmp(string&a,string&b){
    if(a.length()==b.length()){
        int l=a.length();
        for(int i=0;i<l;i++){
            int x=mp[a[i]],y=mp[b[i]];
            if(x==y) continue;
            return x<y;
        }
    }
    return a.length()<b.length();
}
void DP(){
    dt[1]="()"; dt[2]="{}"; dt[3]="[]";
    string s;
    for(int i=4;i<=1000;i++){
        dt[i]=dt[1]; dt[i].append(dt[i-1]);
        for(int j=2;j<i;j++){
            s=dt[j];
            s.append(dt[i-j]);
            if(cmp(s,dt[i]))
                dt[i]=s;
        }
        if(i%2==0){
            s="(";
            s.append(dt[i/2]);
            s.push_back(')');
            if(cmp(s,dt[i]))
                dt[i]=s;
        }
        if(i%3==0){
            s="{";
            s.append(dt[i/3]);
            s.push_back('}');
            if(cmp(s,dt[i]))
                dt[i]=s;
        }
        if(i%5==0){
            s="[";
            s.append(dt[i/5]);
            s.push_back(']');
            if(cmp(s,dt[i]))
                dt[i]=s;
        }
    }
}
int main(){ios::sync_with_stdio(false);cin.tie(0);
    int T,n;
    cin>>T;
    DP();
    auto solve = [=](int x) {
        cout << dt[x] << '\n';
    };
    while (T--){
        cin>>n;
        solve(n);
    }
}

 

궁금한 점이 있으시다면 질문 남겨주세요 :)