[백준] 1107번: 리모컨 문제 풀이 파이썬

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

접근 방법

해당 문제는 브루트포스 탐색이 필요한 문제로, 범위 내 가능한 모든 수를 비교하여 최소 버튼 횟수를 구하면 된다.
범위 내 고장나지 않은 버튼으로 만들 수 있는지 검사하고, 그 숫자와 목표 채널의 차이를 구한다.
여기서 중요한건 낮은 숫자부터 올라가는 것과 높은 숫자부터 내려가는 경우를 고려한다.
최대 입력 가능한 N인 500,000을 입력 받았다면, 1~500,000 사이의 최소 횟수보다 500,000 ~ 1,000,000 사이의 최소 횟수가 더 적을 수도 있다는 의미이다.

전체코드

from sys import stdin
input = stdin.readline

N = int(input())
M = int(input())

# 망가진 버튼이 없으면 리스트 입력 받지 않음
if M > 0:
    broken_button = list(map(str, input().split()))
else:
    broken_button = []

# 이동하려는 채널이 시작 채널과 같으면 0
if N == 100:
    print(0)
else:
    # 최대 횟수는 목표 채널까지 +만 눌렀을 때의 횟수
    minCnt = abs(N - 100)
    # 입력 제한은 500000이지만
    # 1부터 500000까지의 차이와
    # 1000000부터 500000까지의 차이도 고려해야함
    for num in range(1000001):
        possible = True
        # 모든 경우의 수를 검사하면서
        # 해당 숫자가 고장난 버튼의 숫자인지 검사
        for i in str(num):
            if i in broken_button:
                possible = False
                break
        # 가능한 숫자라면
        if possible:
            # 최소 횟수는 숫자버튼을 누르는 횟수와 +혹은-를 누르는 횟수의 합
            minCnt = min(minCnt, len(str(num)) + abs(num - int(N)))

    print(minCnt)

알고리즘을 하나도 모르던 시절에는 모든 문제를 브루트포스로 접근했었는데, 요새는 브루트포스로 접근하지 않으려는 경향이 생겨서 그런지 접근 방식을 찾는 데에 시간이 좀 걸린 것 같다.