2529 부등호
알고리즘(브루트포스, 백트래킹)
1
2
3
1. 모든 경우를 탐색하되, 앞에서부터 하나씩 채워가면서 재귀형태로 하면 백트래킹도 적용하기 쉽다.
2. 조건에 맞는 경우만 탐색하면 됨.
3. 낮은 거 먼저 탐색하도록하면 굳이 뭘 저장할 필요없이 맨처음것만 minimum에 저장하고, 제일 나중 것을 maxnimum에 저장하면 된다.
코드
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
#include <iostream>
using namespace std;
int N, arr[10];
char str[9], mini[10], maxi[10];
bool check[10], isMini;
void brute(int deep);
int main() {
cin >> N;
for (int i = 0; i < N; i++)
cin >> str[i];
for (int i = 0; i < 10; i++) {
arr[0] = i;
check[i] = true;
brute(0);
check[i] = false;
}
cout << maxi << endl;
cout << mini << endl;
}
void brute(int deep) {
if (deep == N) {
if (!isMini) {
for (int i = 0; i < N + 1; i++)
mini[i] = arr[i] + '0';
isMini = true;
}
for (int i = 0; i < N + 1; i++)
maxi[i] = arr[i] + '0';
cout << "check : " << maxi << endl;
return;
}
if (str[deep] == '>') {
for (int i = 0; i <= arr[deep] - 1; i++) {
if (!check[i]) {
arr[deep + 1] = i;
check[i] = true;
brute(deep + 1);
check[i] = false;
}
}
}
else {
for (int i = arr[deep] + 1; i <= 9; i++) {
if (!check[i]) {
arr[deep + 1] = i;
check[i] = true;
brute(deep + 1);
check[i] = false;
}
}
}
}