💡 문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
💭 접근
이 문제는 고장난 버튼을 제외한 나머지 버튼과 +, - 버튼만을 사용하여 원하는 목표채널로 가는 최소를 구하는 문제이다. 문제 풀이 과정은 다음과 같다.
- 우선, 돌리고자 하는 채널에 대해서 +, -만을 사용하여 이동하는 것이 최대값이므로 초기의 ans 값을 (목표 채널 - 100)의 절대값으로 지정해준다.
- 0~1,000,000 까지의 숫자(channel)을 돌면서 channel안에 고장난 버튼의 숫자가 있는지 확인한다.
- channel에 고장난 버튼의 숫자가 없다면, ans값과 비교해주면 되는데, 이때 channel의 자릿수 + (목표채널 - channel)과 비교한다.
여기서 channel의 자릿수는 간단하게 channel을 문자열로 변환하여 len() 함수를 사용하였고, 자릿수를 더해주는 이유는 channel로 이동할 때 누르는 숫자 버튼의 횟수이다. 정리하면,
(channel로 이동할 때 숫자버튼을 누르는 횟수)에,
(목표채널까지 + 또는 -를 누르는 횟수)를 더한 값과 비교하는 것이다.
또한 for-else 구문을 이용하여 고장난 버튼이 있을경우 break를 하여 ans값을 갱신하지 않도록 구현하였다.
여기서 한가지 더 살펴볼 점으로 channel을 1,000,000 까지 반복하는 이유는 주인공이 이동하고자 하는 채널의 최대는 500,000 이고, 전체 채널의 갯수는 제한이 없기 때문에 예를 들어,
n = 500,000 이고 고장난 숫자가 2, 3, 4 라면, 111,111에서 388,889번 이동하는 것 보다 511,111에서 11,111번 이동하는 것이 더 적을 수 있기 때문에 이와 같은 더 큰 경우까지 모두 고려하여 1,000,000 까지 반복한다.
📒 코드
n = int(input())
m = int(input())
bnt = []
if m != 0:
bnt = list(map(int, input().split()))
ans = abs(n - 100)
for channel in range(1000000):
for num in str(channel):
if int(num) in bnt:
break
else:
ans = min(ans, len(str(channel)) + abs(n - channel))
print(ans)💭 후기
channel 값을 문자열과 정수형으로 왔다갔다 하는 부분을 생각해내기가 까다로웠다.
🔗 문제 출처
https://www.acmicpc.net/problem/1107
