[BOJ] 1107번 - 리모컨

---

문제설명

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

1107번: 리모컨

사고과정

• 중복을 허용하는 순열 product 라이브러리를 활용하려고 노력했다. 문제에서 잡아내야 할 포인트들은 다음과 같다.
• 1. 고장난 숫자 버튼을 제외하고 숫자 순열 경우의 수를 만든 후 +/- 를 사용해서 원하는 채널로 가기
• 2. 시작채널 100으로부터 +/-만 사용해서 원하는 채널로 가기
• 3. 문제에서 채널은 무한대까지 있다고 했다. 이를 캐치해야 했어야 함. 주어지는 채널 수 범위는 50만이지만 움직일 수 있는 채널은 무한대까지 이기 때문에 50만 채널에 도달하는 방법이 오름차순으로 도달하는 방법도 있지만 50만 1에서 50만으로 가는 내림차순으로 도달하는 방법도 있다.
• 약 1시간 반정도 풀려고노력했는데, 어떤 반례에서 테스트를 통과하지 못하는지 찾지 못했다. 질문 게시판을 다 뒤져가면서 찾아보았는데도 못 찾았다. 질문 게시판에 있는 반례는 다 맞았는데..
• 그래서 구글링을 해서 풀이를 보았는데 매우 간결한 풀이를 보았다. 이 분은 product를 사용하는 것이 아니라 일반 for loop 숫자를 0부터 100만(이 때, 100만으로 설정한 이유는 50만 채널에 도달하기 위해서 내림차순으로 가기 위함!)으로 설정했는데, 이 때 loop도는 숫자를 '채널 번호'라고 세운 것! 이게 정말 인상적이었다. 
• Loop를 돌면서 해당 채널 번호에 사용된 숫자 버튼들이 주어진 고장난 버튼 숫자 목록안에 속한다고 하면 바로 False를 리턴해서 그냥 시작 채널에서 +/-만 사용하도록 처리해주었다. 어차피 최소버튼 개수만 구하면 되므로 그렇게 처리한 듯하다. 
• 대단한 풀이들이 정말 많은 듯 하다...

풀이(스스로 못 푼 풀이)

import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
broken = list(input().rstrip())
# 시작 채널 100에서 + 또는 - 만 사용할 경우
result = abs(n - 100)

def check(channel):
    channel = list(str(channel))
    for c in channel:
        # 채널 숫자버튼이 하나라도 고장난 버튼이라면 False
        if c in broken:
            return False
    return True

# i가 채널이라고 가정 -> 100만까지 도는 이유: 채널을 50만 넘어가게 한다음 -채널 하는게 더 적은 경우도 있음
for i in range(0, int(1e6)+1):
    if check(i):
        result = min(result, len(str(i)) + abs(n - i))

print(result)