Algorithm/BOJ
KOI 2019 고등부 2차 / 괄호 - 17623
jhg0406
2020. 7. 31. 14:26
|
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
|
#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]);
}
}
|
cs |
https://www.acmicpc.net/problem/17623
17623번: 괄호
6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해
www.acmicpc.net
괄호
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 인 경우만 고려해서 틀린 답을 구했습니다.
