백준 1107번 리모컨 - 파이썬

 

1107번: 리모컨

이 문제는 브루트포스 - 완전탐색 문제로, 말그대로 모든 경우의 수를 찾는 문제다.

문제를 읽고 두 가지 경우로 크게 나눌 수 있다. 

1. +, - 버튼으로만 조작해서 채널 이동

2. 고장난 번호를 피해서 target 채널과 최대한 가까운 채널로 이동한 후, target 채널까지 +, -를 눌러서 이동

일단 만들 수 있는 모든 채널을 구한 후, 그 채널 번호가 tartget 채널과의 차이가 최소인 것을 찾으면 답을 찾으면 된다.

import sys
input = sys.stdin.readline
target = int(input())
n = int(input())
if n > 0:
    broken = list(map(int,input().split()))
else:# 고장난 채널이 없을 경우
    minCount = abs(100 - target)
    minCount = min(minCount, len(str(target)))
    print(minCount)
    exit(0)
minCount = abs(100 - target)# +, - 로만 이동했을 때 count

for num in range(1000001):
    num = str(num)

    for i in range(len(num)):
        if int(num[i]) in broken:
            break
        elif i == len(num) - 1:# 모든 채널 번호가 고장난 번호가 아닐 때
            minCount = min(minCount, abs(int(num) - target) + len(num)) 
print(minCount)

*만약 고장난 채널 개수 n이 0일 경우,

처음 채널이 시작하는 채널 번호가 100 이기 때문에

채널 번호 1400 말고도(이 때 답은 len써서 4개) 예를 들어 100 이 target일 때 답은 0 이 나와야 하므로,  minCount = min(minCount, len(str(target))) 과 같이 채널의 길이와 비교하는 코드도 꼭 넣어줘야한다.

* 왜 범위는 100만 일까?

문제에 제시된 target 채널 번호는 50만 이다. 하지만 채널 번호 자체는 무한대 이기 때문에 만약 target이 50만 이고 1~8 번호가 고장 났다면? 그렇다면 채널 번호를 90만 까지 갔다가 +,-로 이동해서 40만번 + @ 답이다. 그렇기 때문에 채널의 범위는 100만으로 잡았다. 

참고자료

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