문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

www.acmicpc.net/problem/1107

  • 입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

  • 출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

과정

이 문제는 부르트포스 알고리즘으로 해결하는 문제다. Brute(난폭한)와 Force(힘)가 합쳐져서 난폭하게 힘으로 때려맞추는 알고리즘으로, 완전탐색이라는 번역어처럼 무차별적으로 전부 대입해서 때려맞추는(?) 알고리즘이다.

마치 4자리 비밀번호를 풀기 위해서 0000부터 9999까지 가능한 수를 전부 맞춰보는 것에 비유할 수 있다.

이 문제에서는 0부터 1,000,000까지 가능한 모든 경우를 비교해보는 것이다.

그런데 채널이 500,000까지인데 왜 1,000,000까지 비교할까? 500,000까지만 탐색하면 큰 채널에서 작은 채널로 -를 했을 때를 비교할 수 없기 때문이다.

예를 들어 원하는 채널이 450,000인데 1~7까지의 버튼이 고장난 경우 채널 800,000번에서 450,000으로 내려오는 것이 정답이 된다.

n = input()
str_len = len(n)
n = int(n)
m = int(input())
broken = list(map(int, input().split()))

if n == 100:
    print(0)
elif m == 0:
    print(min(str_len, abs(n - 100)))
else:
    res = abs(n-100)
    for i in range(1000000):
        tmp = i
        flag = 0
        while tmp:
            if tmp%10 in broken:
                flag = 1
                break
            tmp //= 10
        if flag:
            continue
        res = min(res, str_len + abs(n-i))
    print(res)

오잉 하지만 첫 번째 시도는 실패했다. 이유를 한참 찾았는데, 숫자 i를 계속 10으로 나누는 방법으로 자리수를 검사하면 i가 0인 경우는 아예 검사하지 않고 넘어가기 때문이다.

최종 코드

따라서 i를 문자열로 바꿔서 문자열을 순서대로 탐색하는 것으로 방법을 바꾸었다.

n = int(input())
m = int(input())

# m == 0인 경우 고장난 버튼 번호를 받지 않고 종료
if m == 0:
    print(min(len(str(n)), abs(n - 100)))
else:
    broken = list(map(int, input().split()))
    res = abs(n-100)
    for i in range(1000000):
        flag = 0
        for x in list(str(i)):
            # 현재 숫자 중 하나라도 누르지 못하는 숫자가 있으면 다음으로 넘어감
            if int(x) in broken:
                flag = 1
                break
        if flag:
            continue
        res = min(res, len(str(i)) + abs(n-i))
    print(res)

참고 사이트