KOI 2019 고등부 2차 / 괄호 - 17623

#include <iostream>
using namespace std;
 
string dp[1001];
 
string min(string s1, string s2) {
    if(s1.size() == 0) return s2;
    if(s1.size() == s2.size()) {
        for(int i = 0; i<s1.size(); ++i)
            if(s1[i] < s2[i]) return s1;
            else if(s1[i] > s2[i]) return s2;
    }
    else if(s1.size() < s2.size()) return s1;
    return s2;
}
 
void convert(string& s) {
    for(int i = 0; i<s.size(); ++i) {
        switch(s[i]) {
            case '1': cout << "(";
            break;
            case '2': cout << ")";
            break;
            case '3': cout << "{";
            break;
            case '4': cout << "}";
            break;
            case '5': cout << "[";
            break;
            case '6': cout << "]";
        }
    }
    cout << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int C;
    cin >> C;
    dp[1] = "12";
    dp[2] = "34";
    dp[3] = "56";
    for(int i = 4; i<=1000; ++i) {
        for(int j = 1; j<i; ++j)
            dp[i] = min(dp[i], dp[j]+dp[i-j]);
 
        if(i % 2 == 0) dp[i] = min(dp[i], "1" + dp[i/2] + "2");
        if(i % 3 == 0) dp[i] = min(dp[i], "3" + dp[i/3] + "4");
        if(i % 5 == 0) dp[i] = min(dp[i], "5" + dp[i/5] + "6");
    }
    int N;
    for(int tn = 0; tn<C; ++tn) {
        cin >> N;
        convert(dp[N]);
    }
}

 

 

 

 

 

 

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

17623번: 괄호

 

 

 

 

 

 

괄호

DP로 해결 할 수 있습니다.

dp[i]를 i를 만들수 있는 괄호의 조합중 dmap이 가장 작은것 이라고 한다면

i = a + b(a, b는 자연수)로 표현할 수 있고

따라서 dp[i] 는 dp[a] + dp[b]가 최소가 되는 a와 b의 조합을 찾으면 됩니다.

추가로, 전체를 감싸는 경우도 생각해 주어 i가 2, 3, 5로 나누어 떨어질 경우도 고려해주면 됩니다.

 

 

오답노트)

처음엔 i = a+b를 생각하지 못하고 덧셈에 대해서 i-1, i-2, i-3 인 경우만 고려해서 틀린 답을 구했습니다.