BOJ-1107 리모컨
https://www.acmicpc.net/problem/1107
문제 소개
이동하고자 하는 채널과 고장난 버튼에 대한 정보가 주어졌을 때 버튼을 누르는 최소 횟수를 구한다.
버튼은 0부터 9까지의 숫자 버튼과 +, - 버튼이 있다. + 버튼과 - 버튼은 누를 시 각각 채널을 1씩 +/-로 이동시킨다.
시작 채널은 100번이다.
문제 풀이
입력값으로 이동하고자 하는 채널인 n과 고장난 버튼의 개수인 m을 차례로 받는다.
m이 0이 아닌 경우에만 추가적으로 고장난 버튼의 정보를 입력받는다.
m에 따라 경우를 나누기
먼저 입력 데이터를 고장난 버튼의 개수가 몇 개인지에 따라 나누었는데, 간단한 두 경우를 먼저 알아보면 아래와 같다.
- 고장난 버튼이 없는 경우
n이 100인 경우 : 이미 도착했으므로 0을 출력한다.그 외의 경우 : 버튼을 하나씩 누른 경우와 100에서 시작하여 + 또는 - 를 눌러 도착한 경우 중 횟수가 적은 경우를 출력한다.
- 버튼이 모두 고장난 경우 : 100에서 시작하여 + 또는 -를 누른 횟수를 출력한다.
위 두 경우는 간단하게 최소 횟수를 구할 수 있다. 하지만 일부 버튼만 고장난 경우는 고려할 사항이 조금 더 있다.
일부 버튼만 고장난 경우
이 경우에는 여러 후보군을 담아두는 리스트인 cand를 선언하여 각 후보군에서의 버튼 횟수를 구하도록 하였다.
첫번째 후보
먼저 버튼을 누르는 횟수를 최소화 하는 방법을 단순히 생각해 보면, n의 앞에서 순서대로 버튼을 누를 수 있는 동안 계속 누르다가 누를 수 없는 버튼이 나오면 + 또는 - 버튼의 횟수를 최소로 하도록 나머지 자리를 채우는 것이 되겠다.
아래의 경우를 생각해 보자.
1
2
3
5457
3
6 7 8
5, 4, 5 까지는 누를 수 있지만 7은 고장났으므로 7에서 가장 가까운 입력할 수 있는 수인 5 또는 9를 마지막으로 누른 후 + 또는 -를 누르게 된다.
두번째 후보
다른 방법으로는 n과 같은 자릿수를 가지지만, 가장 큰 자리의 수가 다른 숫자에서 접근하는 경우이다.
아래의 경우를 생각해 보자.
1
2
3
199
1
9
188을 입력하여 +를 11번 누르는 것보다 200을 입력하여 -를 한 번 누르는 것이 더 횟수가 적다.
세번째 후보
n의 자릿수를 x라고 했을 때, (x - 1) 자릿수에서 + 버튼만 눌러서 도착하는 경우와 (x + 1) 자릿수에서 - 버튼만 눌러서 도착하는 경우를 생각해 볼 수 있다.
(x - 1) 자릿수의 경우, n의 자릿수가 1 보다 커야 고려가 가능하다.
(x + 1) 자릿수의 경우, 입력 가능한 버튼 중 최솟값이 0인 경우를 따로 처리해 주어야 한다. (수의 맨 앞에 0이 올 수 없기 때문이다)
세번째 후보는 첫번째 후보를 구하는 중 누를 수 없는 버튼을 만났을 경우에만 구한다. 고장난 버튼을 만나지 않은 경우가 다른 자릿수에서 출발하는 경우보다 무조건 횟수가 적기 때문이다.
결과
마지막으로 리스트 clicks에 각 후보에 대한 횟수를 구하여 삽입한다.
횟수는 (후보의 자릿수) + (+/- 버튼의 횟수) 이다. 물론 후보가 100인 경우 (+/- 버튼의 횟수)만 구한다.
정답인 clicks의 최솟값을 출력한다.
코드
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from sys import stdin
input = lambda: stdin.readline().rstrip()
# 시작 채널은 100
n = input()
m = int(input())
# 고장난 버튼이 없는 경우
if m == 0:
if n == "100":
print(0)
else:
print(min(abs(int(n) - 100), len(n)))
# 버튼이 모두 고장난 경우
elif m == 10:
arr = list(map(int, input().split()))
print(abs(int(n) - 100))
# 일부 버튼만 고장난 경우
else:
arr = list(map(int, input().split()))
if n == "100":
print(0)
else:
buttons = {i: True for i in range(10)}
for i in arr:
buttons[i] = False
cand = [100]
t = [i for i in buttons.keys() if buttons[i]]
# 두번째 후보
# n과 자릿수가 같으면서 가장 높은 자리의 수만 다른 수들을 후보군에 포함
for i in range(int(n[0]) - 1, 0, -1):
if buttons[i]:
cand.append(int(
str(i) + str(t[-1]) * (len(n) - 1)
))
break
for i in range(int(n[0]) + 1, 10):
if buttons[i]:
cand.append(int(
str(i) + str(t[0]) * (len(n) - 1)
))
break
number = ""
for i in n:
# 해당 버튼을 누를 수 있는 경우
if buttons[int(i)]:
number += i
if number == n:
print(min(abs(int(n) - 100), len(n)))
break
continue
# 해당 버튼이 고장난 경우
else:
# 세번째 후보
# (len(n) + 1)자릿수에서 -만 눌러서 이동하는 경우 고려
# 0을 누를 수 있는 경우와 아닌 경우를 고려
if t[0] == 0:
if len(t) != 1:
cand.append(int(str(t[1]) + str(t[0]) * len(n)))
else:
cand.append(int(str(min(t)) * (len(n) + 1)))
# n의 길이가 1보다 큰 경우에만 (len(n) - 1)자릿수에서 +만 눌러서 이동하는 경우를 고려함
if len(n) > 1:
cand.append(int(str(max(t)) * (len(n) - 1)))
# 첫번째 후보
for j in range(int(i) - 1, -1, -1):
if buttons[j]:
cand.append(int(
number + str(j) +
str(max(t)) * (len(n) - len(number) - 1)
))
break
for j in range(int(i) + 1, 10):
if buttons[j]:
cand.append(int(
number + str(j) +
str(min(t)) * (len(n) - len(number) - 1)
))
break
# 각 후보에 대한 횟수 구하기
clicks = []
for j in cand:
if j == 100:
clicks.append(abs(int(n) - j))
else:
clicks.append(abs(int(n) - j) + len(str(j)))
# print(cand)
# print(clicks)
print(min(clicks))
break