브루트 포스 : 리모컨

#1107 리모컨 https://www.acmicpc.net/problem/1107

1107번: 리모컨

이것도 쓸데없는 고민을 참 많이했다.

 

난 좀 단순하게 생각해볼 필요가 있을 듯 하다.

 

simple is best!!

 

target = int(input())
n = int(input())
broken = []
if n > 0:
    broken = input().split()

answer = abs(target-100)

for num in range(1000001):
    for n in str(num):
        if n in broken:
            break
    else:
        answer = min(answer, len(str(num)) + abs(target-num))

print(answer)

내가 의문을 품었던 부분은 딱 하나다.

 

왜 백만까지 순회해야하는가?

 

답은

 

입력값은 50만이 최대이지만 채널은 무한대까지 존재할 수 있다.

쉽게 말하면, 500000번 채널에 도달하기 위해서 600000번 채널을 거쳐갈 수 있다.

 

이해가 됐는가?

그래서 최대 도달값은 백만이 되어야한다.

만약 0~8까지의 수를 사용할 수 없을 때에 50만에 도달해야한다면 999999번 채널을 거쳐서 갈 수도 있다. (물론 다른 채널을 거치는게 더 빠르다.)

 

단순한 사고를 추구하자.