algorithm'''problem solve
[백준] 1107 - 리모컨 (브루트포스)
JunHwa Park
2020. 10. 21. 13:35
https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼��
www.acmicpc.net
|
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
|
n = int(input())
m = int(input())
lost = list()
if m > 0:
lost = list(map(int, input().split()))
if n == 100:
print(0)
elif n > 100:
minv = 100
maxv = 100
for i in range(n, 100, -1):
s = str(i)
flag = True
for c in s:
if int(c) in lost:
flag = False
if flag:
minv = i
break
for i in range(n, 2 * n - minv):
s = str(i)
flag = True
for c in s:
if int(c) in lost:
flag = False
if flag:
maxv = i
break
if maxv == 100:
val = (minv, abs(n - minv))
else:
val = (maxv, abs(n - maxv))
print(min(abs(100 - n), len(str(val[0])) + val[1]))
else:
minv = 100
maxv = 100
for i in range(n, 100):
s = str(i)
flag = True
for c in s:
if int(c) in lost:
flag = False
if flag:
maxv = i
break
for i in range(n, -1, -1):
s = str(i)
flag = True
for c in s:
if int(c) in lost:
flag = False
if flag:
minv = i
break
if abs(n - minv) > abs(n - maxv):
val = (maxv, abs(n - maxv))
else:
val = (minv, abs(n - minv))
print(min(abs(100 - n), len(str(val[0])) + val[1]))
|
cs |
브루트포스로 탐색하면 된다.
n에서 시작해서 고장나지 않은 버튼으로 만들 수 있는 수를 찾으면 '숫자 버튼으로만' 만들 수 있는 가장 가까운 값이 2개 나온다.
그 중에서 더 가까운 값을 찾고, 그 값과 오직 +나 -만 이용했을 때 더 적게 누르는 값을 찾으면 된다.
다만, n이 100보다 클 경우, n에서 작은 수 중에서 숫자 버튼으로 만들 수 있는 경우를 찾고, 이를 초과하지 않는 선에서 큰 수를 찾는 것이 좋다. 안그러면 시간초과 가능성이 있다.