백준 - 1107 리모컨

문제

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

풀이

브루트 포스를 이용하면 해결할 수 있는 문제
문제에서 요구하는 부분은 최소한의 버튼을 눌러서 원하는 채널로 이동해야한다.
초기 채널은 100번, 만약 101번 채널을 이동해야하고 고장난 버튼이 없다면 할 수 있는 행동으로는 1,0,1 버튼 3개를 눌러 이동하는 방법, 100번 채널에서 + 버튼을 눌러 이동하는 방법이 있다. 그렇다면 문제에서 요구하는 버튼 이동 방법은 + 버튼 한번만 눌러 이동하는 방법이다.
이런 방법으로 문제를 접근해야한다. 그렇다면 버튼 이동 방법을 다음과 같이 정리할 수 있다.

1. '+' 또는 '-' 버튼만 눌러서 이동한다.
2. 고장난 버튼이 없다면 해당 버튼만 눌러서 이동한다.
3. 고장난 버튼을 제외하고 최대한 이동해서 '+','-' 버튼을 눌러 목표 채널에 도달한다.

이 이동 방법을 어떻게 표현할 것인지 중요하다.
일반적으로 '+' 또는 '-' 버튼만 눌러서 이동하는 경우, 버튼을 최대한 많이 눌러서 이동한다. 예를 들어 5457번 채널로 이동해야하고, 6,7,8번 버튼이 고장날 경우
5357번 '+' 버튼을 눌러서 이동하면 도달 할 수 있다. 또는 5455번 버튼을 누르고, '+' 버튼을 두번 누르면 버튼을 6번만 눌러서 도달 할 수 있다.
하지만 위의 101번 채널을 이동하는 예제에서는 '+' 버튼만 누르는 것이 정답이다.
이런 방법으로 버튼을 누르는 횟수를 비교하여 항상 최솟값을 출력해야한다.

소스코드

import sys
N = sys.stdin.readline().rstrip()
M = int(sys.stdin.readline())

def broken_checker(numbers: str, brokens: list):
    for i in numbers:
        if int(i) in brokens:
            return False
    return True

if M == 0:
    print(min(len(N),abs(int(N)-100)))
else:
    broken = list(map(int,sys.stdin.readline().split()))
    counter = abs(int(N)-100)
    for i in range(1000001):
        if broken_checker(str(i),broken):
            counter = min(counter, abs(int(N)-i)+len(str(i)))
    print(counter)

소스코드에서도 숫자 문자열의 길이가 숫자 버튼을 누르는 횟수이고 이것을 최대한의 범위에서 하나씩 고장난 버튼이 포함되어있는지 조사, 그리고 고장난 버튼이 아니라면 숫자 버튼을 누르는 횟수 + 숫자버튼으로 채널 이동 후 '+','-' 버튼을 누르는 횟수를 비교하면 정답을 낼 수 있다.