백준17623 괄호

작성일 | In

문제 링크

  • http://icpc.me/17623

문제 출처

  • 2019 KOI 고등부 2번

사용 알고리즘

  • DP

시간복잡도

  • $O(N^2 \log N)$

풀이

문자열에 대한 DP를 하면 됩니다.

모든 $N$에 대해 길이가 $O(\log N)$인 정답이 존재하기 때문에 $O(N^2 \log N)$에 정답을 전처리할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

bool Compare(const string &s1, const string &s2){
    if(s1.size() != s2.size()) return s1.size() < s2.size();
    static unordered_map<char, int> mp = {
        {'(', 1}, {')', 2},
        {'{', 3}, {'}', 4},
        {'[', 5}, {']', 6}
    };
    for(int i=0; i<min(s1.size(), s2.size()); i++){
        if(s1[i] != s2[i]) return mp[s1[i]] < mp[s2[i]];
    }
    return false;
}

string D[1010];
void Init(){
    D[1] = "()"; D[2] = "{}"; D[3] = "[]";
    for(int i=4; i<=1000; i++){
        D[i] = D[1] + D[i-1];
        for(int j=2; j<i; j++){
            string tmp = D[j] + D[i-j];
            if(Compare(tmp, D[i])) D[i] = tmp;
        }
        if(i % 2 == 0){
            string tmp = "(" + D[i/2] + ")";
            if(Compare(tmp, D[i])) D[i] = tmp;
        }
        if(i % 3 == 0){
            string tmp = "{" + D[i/3] + "}";
            if(Compare(tmp, D[i])) D[i] = tmp;
        }
        if(i % 5 == 0){
            string tmp = "[" + D[i/5] + "]";
            if(Compare(tmp, D[i])) D[i] = tmp;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    Init();
    int T; cin >> T;
    while(T--){
        int N; cin >> N;
        cout << D[N] << "\n";
    }
}