[백준] 1107번: 리모컨

문제링크

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

접근 방법

쓸 수 있는 버튼으로 만들 수 있는 모든 경우를 찾고 최솟값을 비교한다.
목표 채널보다 자릿수가 한자리 큰 경우까지 고려해 큰 수에서 -로 내려가는 경우까지 고려한다.
가능한 수를 찾을 때는 재귀함수를 이용해 중복순열로 찾는다.

모든 버튼을 사용할 수 있는 경우는 처음의 if문으로 걸러 빠르게 정답을 출력하도록 처리한다.
일반적인 경우 (사용 가능한 버튼의 개수) ^ (목표 채널의 자릿수) 의 개수만큼 경우의 수를 비교하고,
최악의 경우엔 (목표 채널의 자릿수가 10만(10^5)이고, 사용 가능한 버튼이 9개인 경우) 9의 6승, 대략 백만개 정도 경우의 수가 나온다.

코드

n = int(input())  # 목표 채널
length = len(str(n))
m = int(input())  # 고장난 버튼 개수

if m == 0:
    print(min(abs(n - 100), len(str(n))))
else:
    troubles = set(input().split())  # 고장난 버튼들
    able_buttons = [str(i) for i in range(10) if str(i) not in troubles]  # 사용 가능한 버튼들
    able_nums = []  # 버튼들로 만들 수 있는 숫자들


    def make_num(buttons):  # 버튼들로 숫자를 만드는 함수 (중복 순열)
        def recursive(num):
            if len(num) <= length + 1:
                if num: # num == ''인 경우 예외 처리
                    able_nums.append(int(num))
            else:
                return

            for button in buttons:
                recursive(num + button)

        recursive('')


    make_num(able_buttons)
    min_count = abs(n - 100)  # 최소 연산 횟수를 저장하는 변수

    for num in able_nums:
        min_count = min(min_count, abs(n - num) + len(str(num)))

    print(min_count)