리모컨

1. 조건

• 초기 채널 : 100번
• N : 이동 채널 ( 0 <= N <= 500,000)
• M : 고장난 버튼 ( 0 <= M <= 10)
• 채널의 갯수 : 무한대

2. 출력

• 100번에서 N번 채널로 이동하기 위한 최소의 수

3. 방식

• 채널이 무한대라 위에서 내려오는 경우도 생각하여 0부터 500,000*2까지 수 범위를 반복하여 최소를 구함

4. 코드

# 리모컨

N = int(input())    # 이동하려는 채널
M = int(input())    # 고장난 버튼 갯수
broken = set()  # 고장난 버튼이 0개 일 수 있으므로 빈 set으로 초기화
if M:   # 고장난 버튼이 있는 경우만 broken을 재할당
    broken = set(input().split())

cnt1 = abs(N - 100) # 100번에서 이동하는 경우
cnt2 = int(1e9)

for num in range(1000001):  # 완전 탐색
    num = str(num)
    if not set(num) & broken:   # set의 교집합이 없는 경우
        tmp = abs(int(num) - N) + len(num)  # 버튼 누름 + 채널 이동 횟수
        if tmp < cnt2:
            cnt2 = tmp

print(min(cnt1, cnt2))  # 적은 값을 출력

• 그리디한 방법도 좋지만, 시간을 보고 완전 탐색도 시간 내 풀기 위한 방법이다.