https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
www.acmicpc.net
어떤 버튼이 고장 났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야 하는지를 구하는 문제이다.
먼저 고장나 있는 버튼을 입력받을 때 최대 10개밖에 안되므로 bool 배열에 미리 체크해놓고 검사해야 할 때 이용한다.
최소 몇 번 이동했는지를 저장해줄 변수 cnt의 초기값으로 n-100을 해서 +나 -버튼만으로 이동하는 경우를 먼저 넣어 놓고 비교를 해나간다.
최소 횟수를 구하기 위해서 모든 채널에서부터 n으로 가는 모든 경우를 구해줄 것이다.
이동할 채널 N은 500,000 까지이지만 버튼이 고장 나 있는 경우 더 뒤의 채널에서 이동하는 게 더 빠를 수 도 있으므로
0번 채널부터 10,000,00번 채널까지의 경우를 모두 해준다.
해당 채널을 누를 때 버튼이 고장 나있는지 매번 확인해주고 고장 나 있는 경우는 누를 수 없으므로 넘어간다.
고장 난 버튼을 검사하기 위해서는 check함수를 구현하였다. 누를 버튼 번호를 받아서 % 연산을 이용해 한 자리씩 떼준다.
떼낸 숫자가 고장난 버튼일 경우 바로 0을 리턴해주고 아닐 경우에는 길이 값을 늘려준다.
고장 난 버튼이 하나도 없을 경우 길이 값을 리턴한다.
(0인 경우는 나눠줄 수 없으므로 따로 처리해줘야 한다!)
길이를 받아왔다면 해당 채널로부터 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
#include <iostream>
using namespace std;
int n, m;
bool broken[11];
int check(int num) {
//0을 나눌 수 없으므로 따로 처리
if (num == 0) {
if (broken[0]) {
return 0;
}
else {
return 1;
}
}
int len= 0;
while (num > 0) {
//num을 한 자리씩 떼서 검사해준다.
//하나라도 고장이면 0을 return
if (broken[num % 10]) {
return 0;
}
//고장나지 않았으면 길이 증가하고 검사한 자리는 없애준다.
len++;
num /= 10;
}
//고장난 버튼이 없었다면 길이를 return
return len;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//input
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x;
cin >> x;
broken[x] = true;
}
int cnt;
//+, - 버튼만 사용하는 경우
cnt = n - 100;
if (cnt < 0) {
cnt = -cnt;
}
//모든 번호 에서 n번으로 이동해보면서 몇 번 눌러야하는지 계산
//번호가 고장나서 누르지 못하는 경우는 넘어간다.
for (int i = 0; i < 1000000; i++) {
//고장났는지 확인해준다.
//고장이 나지 않았다면 버튼을 누르는 횟수를 받아온다.
int len = check(i);
if (len == 0) continue;
//현재 i번을 숫자로 누른 상태에서 N까지
//몇 번 +나 -로 이동해야하는지
int tmp = n - i;
if (tmp < 0) {
tmp = -tmp;
}
if (cnt > tmp + len) {
cnt = tmp + len;
}
}
cout << cnt;
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2529. 부등호 (0) | 2019.07.03 |
|---|---|
| [BOJ] 1748. 수 이어 쓰기 1 (0) | 2019.07.03 |
| [BOJ] 14442. 벽 부수고 이동하기 2 (0) | 2019.06.28 |
| [BOJ] 2206. 벽 부수고 이동하기 (0) | 2019.06.28 |
| [BOJ] 3055. 탈출 (0) | 2019.06.27 |