백준: 1107 리모컨

문제

1107번: 리모컨

 

문제 풀이

 채널 N으로 이동하고자 할 때, M개의 버튼이 고장 나서 고장 난 버튼을 제외하고 +, -를 활용하여 원하는 채널에 접근하기 위해 최소로 리모컨 버튼을 누르는 경우를 반환하는 문제이다. DFS를 통해 탐색을 진행하더라도, python3의 recursive depth를 초과하지 않으므로 DFS로 문제를 풀었다.

 

• 고장 난고장 난 버튼이 없는 경우
  • 채널 100번부터 시작하므로 abs(100 - 이동하고자 하는 채널)과 해당 채널의 수를 버튼으로 입력하였을 때의 크기를 비교해 작은 값을 출력한다.
• 고장 난 버튼이 있는 경우
  • 사용 가능한 버튼을 DFS로 통해 하나씩 추가해가며, depth는 N의 길이만큼 탐색한다.
    • 만약 찾고자 하는 채널이 1234라면, 숫자 버튼을 입력할 경우 4자리 이상 선택할 필요는 없다.
  • abs(N - 사용 가능한 버튼을 통해 입력한 채널)은 +, -를 눌러야 하는 횟수가 된다.

 

코드

from sys import stdin


def dfs(channel, press_cnt):
    global answer

    for button in available:
        cur_channel = int(channel + button)
        remainder = abs(n - cur_channel)
        answer = min(answer, press_cnt + remainder + 1)

        if press_cnt < channel_length:
            dfs(str(cur_channel), press_cnt + 1)


if __name__ == '__main__':
    n = int(stdin.readline())
    channel_length = len(str(n))
    m = int(stdin.readline())
    answer = abs(100 - n)

    if not m:
        print(min(answer, channel_length))
        exit(0)

    available = {str(num) for num in range(10)} - set(stdin.readline().split())
    dfs('', 0)
    print(answer)

 채점 중, 92%와 97%에서 틀렸다고 하였다. M이 0인 경우, 즉 고장난 버튼이 없는 경우 가고자 하는 채널의 크기 (N이 1234인 경우 : 4) 만큼 반영하였는다. 생각해보니, 단순히 +, -로 이동하는 경우가 더 최소일 수 있다는 것을 반영하지 않은 반례를 추가하지 않아서 틀렸었다.😅