[BOJ/백준] 1107 리모컨

# 1107 리모컨
def dfs(cnt,number):
    global min_result,N
    if cnt > 6:
        return
    else:
        if min_result == 0:
            return
        temp = abs(int(number) - N)+cnt
        if temp < min_result:
            min_result = temp
        for k in possible_button:
            dfs(cnt+1,number+str(k))




N = int(input())
K = int(input())
if K != 0:
    button_not = set(map(int,input().split()))
else:
    button_not = set()
allbutton = set(range(10))
possible_button = allbutton - button_not
min_result = abs(N-100)

for i in possible_button:
    dfs(1,str(i))
print(min_result)

 

 

문제를 풀 기본적인 컨셉은 재귀함수를 통해, 모든 경우에 대해서 전부 해보고, 6자리를 넘어가는 경우에는 되돌려줬다. 그리고 각 숫자에서 up,down버튼을 눌렀을때의 경우를 찾아서 결과값을 갱신해주었다.

여기서 처음 틀렸을때는, 아무 버튼도 고장나지않았을때이다. 그래서 입력 오류로 틀렸었다.

 

여기서는 최소가 나오더라도 계속 탐색을 하기 때문에 시간이 많이 걸린다. 개선된 풀이는 다음과 같다.

 

 

N = int(input())
K = int(input())

if K:
    button_not = set(map(int,input().split()))
else:
    button_not = set()

allbutton = set(range(10))
possible_button = allbutton - button_not
down_num = 1000000
up_num = 1000000
min_result = abs(N-100)
for num in range(N,1000001):
    for k in str(num):
        if int(k) not in possible_button:
            break
    else:
        down_num = num
        break

for num in range(N,-1,-1):
    for k in str(num):
        if int(k) not in possible_button:
            break
    else:
        up_num = num
        break
if abs(up_num-N) <= abs(down_num-N):
    close_num = up_num
else:
    close_num = down_num
print(min(len(str(close_num))+abs(N-close_num),min_result))

풀이의 접근은 다음과 같다. 우리가 틀려는 채널의 번호를 기준으로 위아래로 번호를 하나씩 늘리면서 가능한 번호인지 확인한다. 그렇게 구한 두수를 채널 번호와의 차이를 구한다. 그리고 그중에서 차이가 더 적은 번호를 선택을 한다. 만약에 둘의 차이가 같을시에는, 밑에 있는 번호가 자리수가 더 작을수 있으니, 아래번호를 선택한다.

이렇게 구한 채널번호를 누르고 위아래 버튼을 누르는 경우와, 처음부터 위아래 번호를 누르는 경우를 비교해서 더 낮은 경우를 선택한다.