백준 1107 리모컨 (파이썬)

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

1107번: 리모컨

그리디하게 풀려다가 반례가 있어서 모든 경우의 수를 다 계산

 

1. 리스트 a에 버튼에 대한 정보를 저장. 인덱스에 해당하는 버튼이 고장나면 0

2. 고장난 버튼이 있으면 버튼을 입력받고 해당 버튼을 0으로 저장

3. cnt에 버튼을 누르는 횟수의 최소값을 저장. 초기값은 (목표 채널 - 초기채널 100) 으로 설정

4. 가능한 모든 경우의 수를 다 계산해본다

   해당 채널을 누를 수 있으면 최소값을 계산한다

   횟수는 해당 채널에서 +나 -를 누르는 횟수 = abs(n - i) 와 해당 채널을 누르는 횟수 = len(list_i)

import sys

input = sys.stdin.readline

n = int(input())
list_n = list(str(n))
m = int(input())
a = [1 for _ in range(10)]

if m != 0:
    broken = list(map(int, input().split()))
    for i in broken:
        a[i] = 0

cnt = abs(n - 100)
for i in range(1000001):
    list_i = list(str(i))
    flag = 0
    for c in list_i:
        if a[int(c)] == 1:
            continue
        else:
            flag = 1
            break

    if flag:
        continue
    else:
        cnt = min(cnt, abs(n - i) + len(list_i))

print(cnt)