[백준] 1107번 리모콘 - Python

이번에 해결해 볼 문제는 백준에 있는 1107번 카드 구매하기입니다.

---

문제 설명

1. 현재 보고 있는 채널은 100번입니다.
2. 리모콘에 있는 버튼을 눌러 채널을 N번으로 옮기고자 합니다.
3. 그러나 리모콘에 고장난 숫자 버튼이 있습니다.
4. 고장나기 전 사용 가능한 버튼은 0 ~ 9, +, - 이고 고장난 버튼은 입력으로 주어집니다.
5. 단, 이동 가능한 채널은 0번 ~ $\infty$입니다.
6. 이때 채널 N번으로 이동하기위해 버튼을 최소 몇 번 눌러야 하는지 구하면 됩니다.

문제 해결 아이디어

• 해당 문제는 크게 두 가지로 구분할 수 있습니다.
  • 첫째, + 또는 - 버튼을 사용해 채널을 이동시키는 방법
  • 둘째, 직접 숫자를 입력해 채널을 이동시키는 방법
• 위의 두 가지를 구체화하면 아래와 같습니다.
  • 먼저 최소 횟수 기준을 잡기 위해 채널을 +, -로 움직였을 때 횟수(num)를 구합니다.
  • N을 직접 입력하고 싶지만 숫자 버튼이 고장난 경우를 고려해야 합니다. 그러므로 N번 채널과 가까운 채널 중 입력 가능한 채널을 찾아야 합니다. 그렇다면 가까운 채널의 범위를 어떻게 설정해서 탐색을 해야 최소한의 횟수로 탐색을 할 수 있을지 알아보겠습니다.
    • N보다 작은 채널로 이동 후(len(str(N - num))) 다시 +와 - 버튼을 눌러 N번으로 이동해야(N - num) 하기 때문에 N보다 작은 채널의 숫자를 직접 입력해 이동하는 경우 이동 가능한 가장 작은 채널은 N - num + len(str(N - num))입니다.
    • 그렇다면 N보다 작은 채널은 0 또는 N - num + len(str(N - num))이므로 일반화를 시키면 min_num = max(0, N - num + len(str(N - num)))입니다.
    • 그 다음은 N보다 큰 채널을 구하기위해 기준치를 다시 설정해야 합니다. min_num을 N으로 이동시키기 위한 횟수는 len(str(min_num)) + abs(N - min_num))이므로 num = min(num, len(str(min_num)) + abs(N - min_num))와 같이 기준치를 다시 설정할 수 있습니다.
    • 이제 그럼 위에서 작은 채널을 구했던 것처럼 N보다 큰 채널을 max_num = N + num - len(str(N + num))로 구할 수 있습니다.
    • max_num을 N으로 이동시키기 위한 횟수는 len(str(max_num)) + max_num - N이므로 정답은 num = min(num, len(str(max_num)) + max_num - N)으로 구할 수 있습니다.

주의해야 할 점

• 고장난 버튼은 숫자 버튼이라는 점
• 시작 채널이 100번이라는 점
• 제일 작은 채널은 0번이지만 가장 큰 채널은 $\infty$라는 점
• 고장난 버튼이 없을 수도 있다는 점

문제 해결 코드

import sys

input = sys.stdin.readline

N = int(input())
M = int(input())

num = abs(N - 100) # 기준치 : +, - 버튼만 사용해서 이동

if M == 0:
    print(min(len(str(N)), num))
else:
    button = input().split()

    str_N = str(N)

    # N보다 작은 채널로 이동 후 N으로 다시 이동하기 위한 가장 작은 채널
    min_num = int(10e9)
    for n in range(N, max(-1, N - num + len(str(N - num))-1), -1):
        str_n = list(str(n))
        for cha_n in str_n:
            if cha_n in button:
                break
        else:
            min_num = n
            break

    # 기준치 재설정
    num = min(num, len(str(min_num)) + abs(N - min_num))

    # N보다 큰 채널로 이동 후 N으로 다시 이동하기 위한 가장 큰 채널
    max_num = int(10e9)
    for n in range(N, N + num - len(str(N + num)) + 1):
        str_n = list(str(n))
        for cha_n in str_n:
            if cha_n in button:
                break
        else:
            max_num = n
            break

    # 정답 도출
    num = min(num, len(str(max_num)) + max_num - N)

    print(num)