💡문제접근
- 브루트포스 알고리즘으로 모든 경우를 확인해서 조건에 맞는 답을 출력하는 방법을 이용해야한다. 채널번호를 문자로 처리한 다음 for문을 돌려 만약 고장난 버튼이 포함되어 있다면
break를 실행시키고 아니라면 입력한 채널번호의 길이에 이동하려고 하는 채널의 버튼에서 입력한 채널번호를 뺀 값의 절댓값을 더해주면 채널 N으로 이동하기 위해서 눌러야 하는 버튼의 최소 횟수가 나온다.- 처음에는 "최대 채널의 번호가 500,000이니까 for문을 500,000까지 돌려주면 되는거겠지" 이렇게 생각해서
for i in range(500,001)을 입력했는데 틀렸다. 이게 왜 안될까?- 그 이유를 구글링하여 알아봤다. 내가 이동하고 싶은 채널이 N(0 ~ 500,000) 번이라고 했을 때, 0번부터 (+)버튼을 눌러 이동하는 경우와 999,999번부터 (-)버튼을 눌러 이동하는 경우를 전부 고려해야 하기 떄문이다.
- 예를 들어 내가 채널 번호가 500,000인 채널로 이동하려고 하는데 리모콘의 버튼이 0 ~ 8까지가 다 박살이 나서 9번만 누를 수 있는 경우라면 999,999 → 99,999 이런 방법으로 눌러야 한다. 따라서 500,000의 2배로 돌려야 한다.
💡테스트케이스
입력
500000
8
0 1 2 3 4 5 6 7 8
출력
400006
- 버튼을 누르는 과정 : 100 → 99999 → (+)버튼 우다다다.... → 500000
- 5(99,999번의 숫자 길이) + 400001(99,999번에서 500,000번까지 누르는 (+)버튼의 횟수) = 400,006번
💡코드(메모리 : 31388KB, 시간 : 1108ms)
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
button = list(map(str, input().strip().split()))
# 채널의 개수는 0 ≤ N ≤ 500,000이다. 현재 수빈이가 보고 있는 채널의 번호는 100번이다.
# 100번보다 낮은 채널로 이동할 수 있으므로 아래와 같은 값을 넣어준다.
cnt = abs(100 - N)
if N == 100:
print(0)
sys.exit()
else:
for i in range(1000001):
for j in str(i):
if j in button:
break
else:
cnt = min(cnt, len(str(i)) + abs(N-i))
print(cnt)💡소요시간 : 21m
🐢