정보
문제 바로가기 [클릭]
난이도: Gold5
관련 개념: #브루트포스
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 256 MB |
문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
예제 입출력 1
입력
1
2
3
5457
3
6 7 8
출력
1
6
예제 입출력 2
입력
1
2
3
100
5
0 1 2 3 4
출력
1
0
예제 입출력 3
입력
1
2
3
500000
8
0 2 3 4 6 7 8 9
출력
1
11117
예제 입출력 4
입력
1
2
3
100
3
1 0 5
출력
1
0
예제 입출력 5
입력
1
2
14124
0
출력
1
5
예제 입출력 6
입력
1
2
3
1
9
1 2 3 4 5 6 7 8 9
출력
1
2
예제 입출력 7
입력
1
2
3
80000
2
8 9
출력
1
2228
코드(파이썬)
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
def dfs(index, now_cnt, button):
r = now_cnt
# 1. 1234 vs 1234 원하는 길이 도달 (더 이상 탐색할 필요 없음)
if len(target) - len(stack) == 0:
r = min(r, abs(int(target) - int(''.join(map(str, stack)))) + len(str(int(''.join(map(str, stack))))))
# 2. 1234 vs 122ㅁ의 경우 (더 이상 탐색할 필요 없음)
elif target[index-1] != button:
if stack[-1] > int(target[index-1]):
etc = str(min(buttons))
else:
etc = str(max(buttons))
r = min(r, abs(int(target) - int(''.join(map(str, stack)) + etc * (len(target) - index))) + len(target))
# 3. 그 외
elif index < len(target):
for b in get_next(target[min(index, len(target)-1)]):
stack.append(b)
r = dfs(index+1, r, str(b))
stack.pop()
return r
def get_next(num):
start = []
if type(num) == str:
num = int(num)
if len(buttons) > 2:
if num in buttons:
near_button_index = buttons.index(num)
else:
tmp = sorted(buttons.copy() + [num])
near_button_index = tmp.index(num) if tmp.index(num) < len(buttons) else 0
start.append(buttons[near_button_index])
start.append(buttons[near_button_index+1 if near_button_index+1 < len(buttons) else 0])
start.append(buttons[near_button_index-1 if near_button_index+1 > -1 else len(buttons)-1])
else:
start = buttons
return start
stack = []
start = []
cnt2 = 0
target = input().rstrip()
m = int(input())
wrong_buttons = tuple(map(int, input().split())) if m else tuple()
buttons = [i for i in range(0, 10) if i not in wrong_buttons]
result = abs(100 - int(target))
if buttons:
# 자릿수가 차이나는 채널을 따로 계산
digit_p1, digit_m1 = 5000000, 5000000
if len(target) < 6:
if len(buttons) > 1:
if buttons[0] == 0:
digit_p1 = int(str(buttons[1]) + ("0" * len(target)))
else:
digit_p1 = int(str(buttons[0]) * (len(target)+1))
else:
digit_p1 = int(str(buttons[0]) * (len(target) + 1))
if len(target) > 1:
digit_m1 = int(str(buttons[-1]) * (len(target) - 1))
result = min(result, (abs(int(target) - digit_p1) + len(str(digit_p1))), (abs(int(target) - digit_m1) + len(str(digit_m1))))
# 자릿수가 동일한 채널 계산
start = get_next(target[0])
for button in start:
stack.append(button)
result = dfs(1, result, str(button))
stack.pop()
print(result)
특이사항
- 굳이 이렇게 풀어야할까 싶은 풀이로 해결
- 예시 입력:
1 2 3
5001 3 1 4 5
- 1 누를 버튼이 없음 -> 처음채널(100)에서 이동
- 2 누를 버튼이 있음
- 2-1 원하는 채널과 자릿수가 다르면서 차이가 적은 채널 탐색 (예시: 5001, 3, 1 4 5라면 999, 20000)
- 2-2 원하는 채널과 자릿수가 같으면서 차이가 적은 채널 탐색 (예시: 5001, 3, 1 4 5라면 5002)
- 2-3 2-1과 2-2의 결과 중 가장 차이가 적은 채널의 버튼 누른 횟수 계산
- 예시 입력:
- 풀이의 최적화 필요 (손으로 낙서하듯 해결함)
- 일반적인 풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
import sys dest = int(sys.stdin.readline().rstrip()) n = int(input()) ans = abs(100 - dest) if n != 0: broken = set(input().split()) else: broken = set() for i in range(1000001): for N in str(i): if N in broken: break else: ans = min(ans, len(str(i)) + abs(i - dest)) print(ans)
- 간단한 브루트포스 형태
- 문제에 반례가 많은 관계로 다음의 반례모음 링크를 참고하기 바람
참고문헌
-
Comments powered by Disqus.