1107 리모컨
알고리즘(브루트 포스)
1
2
1. 0~100만까지 하나씩 올라가며, 되는지 검사하고, 가장 적게 누르는 건지 저장
2. 되는지 검사할 때는, 고장난 버튼을 bool 배열에 저장하여 바로바로 참조가능하게 하고, 뒤에서부터 하나씩 검사하자
헛발질 기록
1
2
3
1. 처음엔 들어온 버튼의 자릿수에 맞게, 모든 숫자를 검사하되 재귀로 수를 하나씩 채워하는 식으로 하여 안되는 건 미리 제거하는 식으로 함
-> ex) 2528이면 모든 4자리수를 검사하되, 앞에서부터 안되는건 배제하며 채워감
2. 그러나 자릿수를 더 크게 해도 최소가 될 경우가 존재. 따라서 자릿수를 꽉채워서 모든 수를 검사하였으나 설계에 어려움을 느낌
코드
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
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int to;
bool isable[10];
int pushButton();
int check(int cur);
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
cin >> to;
int n, t;
cin >> n;
memset(isable, 1, sizeof(isable));
for (int i = 0; i < n; i++) {
cin >> t;
isable[t] = false;
}
cout << min(abs(100 - to), pushButton());
}
int pushButton() {
int result = 2000000000, end = to * 10;
for (int i = 0; i <= end; i++) {
int length = check(i);
if(length != -1)
result = min(result, abs(to - i) + length);
}
return result;
}
int check(int cur) {
int t = 10, index = 0, end = cur * 10;
if (end == 0)
end = 10;
while (t <= end) {
int c = cur % t;
c = c / (t / 10);
if (!isable[c])
return -1;
t *= 10;
index++;
}
return index;
}