[백준 1107번-파이썬]리모컨

백준 (BOJ) 1107
https://www.acmicpc.net/problem/1107

사용언어 : PYTHON

1.문제

2.풀이

2-1. 시도했다가 실패한 풀이

N : 5457
M : 3
고장난 버튼 : [5,7] 이면
입력이 가능한 버튼들은 [0,1,2,3,4,5,6,8,9]이다.

5457의 첫 번째 숫자 5가 없으므로 첫 번째 숫자를 4 혹은 6을 입력하는 것이 최소로 이동할 수 있는 수가 될 것이다.

이 때 4를 입력한 경우는 뒤에 숫자를 최대한 큰 수로 입력해야 하고, 6을 입력한 경우는 최대한 작은수를 입력해야 한다고 생각하여 문제를 풀고자 했다.

2-2. 올바른 풀이

브루트포스 알고리즘

0 ~ 999899+1 까지 리모컨으로 입력할 수 있는 모든 숫자들을 비교하며 최솟값을 찾는다.

---

N의 범위는 500000까지 이지만 999899까지 비교하는 이유

N=500000, 입력할 수 있는 버튼이 [8,9]일때

100에서 500000까지 + 버튼으로만 이동하는 횟수 = 499900

999899에서 500000까지 - 버튼으로만 이동하는 횟수 = 499899

999899에서 -버튼으로 이동하는 횟수가 정답이 된다.

즉 더 큰 값에서 -버튼으로 이동하는 횟수도 고려하기 위해서 범위를 999899까지 잡았다.

3.코드

초기 최솟값은 100과 목푯값(N)을 +혹은 -버튼으로만 이동하는 횟수 (abs(100-N))으로 뒀다.

0~999899까지의 숫자 중 고장난 버튼이 포함된 숫자가 나올 경우 flag변수를 0으로 바꾸고 반복문을 빠져나온다.

flag변수가 1인경우(=입력할 수 있는 숫자인 경우)는 최솟값을 비교하고 갱신하여 준다.

import sys
import math
input = sys.stdin.readline

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

if M>0:
    err_btn=list(map(int,input().split()))
else:
    err_btn=[]

min_input=abs(100-N)

for num in range(999900):
    flag=1
    num = str(num)

    for i in num:
        if int(i) in err_btn:
            flag=0
            break

    if flag==1:
        min_input=min(min_input,abs(int(num)-N)+len(num))

print(min_input)