백준 | 1107

https://www.acmicpc.net/problem/1107

0~9 중 고장난 버튼이 주어질 때,
현재 채널(100번)에서 원하는 채널(n번)로 이동하기 위한 최소 횟수를 구하는 문제이다.

정상 채널의 최대 번호가 500,000번이므로,
완전 탐색을 고려해 볼 수 있다.

왜냐하면 500,000번이 원하는 채널이라고 해도,
-를 사용하여 접근하는 최악의 경우도 1,000,001번 채널 정도까지만 고려하면 되기 때문이다.

거쳐가는 채널에 고장난 번호가 포함된 경우는 고려하지 않는다.

만약 모든 번호가 고장나지 않았다면,
그 번호를 통해 원하는 채널까지 도달할 수 있는 횟수와 현재 최소 횟수를 비교하는 과정을 반복한다.

코드(정답)는 다음과 같다.

import sys


n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
broken_btn = list(sys.stdin.readline().split())

# 번호 사용 없이 +/-로만 원하는 채널로 이동하는 경우
min_press = abs(n - 100)
# 거쳐가는 채널을 0번부터 1000001번까지 고려
for channel in range(1000001):    
    for c in str(channel):
        # 거쳐가는 채널에 고장난 숫자가 하나라도 포함된 경우
        # 거쳐가는 채널에 직접 도달할 수 없으므로 패스
        if c in broken_btn:
            break
    # 거쳐가는 채널에 직접 도달할 수 있는 경우
    else:
        # (현재 최소 횟수)와 (거쳐가는 채널을 누르는 횟수 + 거쳐가는 채널에서 원하는 채널까지 +/-로 이동하는 횟수)를 비교
        min_press = min(min_press, len(str(channel)) + abs(n - channel))

print(min_press)