1 분 소요

1107번 : 리모컨

1107: 리모컨

방법 1 (틀림)

  • 내가 생각한 방법

    • 목표 숫자(n) 과 최대한 일치하게 같은 자리의 수(result) 만들기 (문자열로 입력받은 n을 훑으며 정수화하기)

      • 해당 숫자의 버튼이 고장났다면 정상 버튼 중 최대한 가까운 버튼으로
      • (이 과정에서 RuntimeError (NameError)가 발생한 것 같음)
    • result에서 +/- 통해 목표값으로 만들기

  • 문제점 1
    • 문제 조건 상, min_btn은 무조건 초기화된다고 생각했는데, 실제로는 그렇지 않음(btns 이 없는 경우도 있기 때문)
  • 문제점 2
    • 모든 경우를 만족시키지 않음 (abs(num-btn)으로 판단하면 안 됨)
    • 반례)
      • n = 1505
      • 정상작동 버튼: 0, 1, 4, 6, 9
      • 작성한 코드는 result를 1404/1406/1604/1606/…이라 생각할 것
      • 하지만 1404/1606이 되면 안됨
import sys
input = sys.stdin.readline

n = input().rstrip()
m = int(input())
btns = set(i for i in range(0, 10)) - set(map(int, input().split()))
result = 0

cnt = 0
# 같은 자릿수 만들기
for num in n:
    num = int(num)
    # 버튼이 정상작동 하는 경우
    if num in btns:
        result *= 10
        result += num
        cnt += 1
    # 버튼이 고장난 경우
    else:
        min_value = 100
        for btn in btns:
            if min_value >= abs(num - btn):
                min_value = abs(num-btn)
                min_btn = btn
        result *= 10
        result += min_btn
        cnt += 1
# 동일한 채널이 나올 때 까지 + / - 버튼 누르기
if result != int(n):
    cnt += abs(result - int(n))

print(min(cnt, abs(100-int(n))))

방법 2 (옳은 풀이)

  • 그냥 모든 경우를 다 따져봄!
  • 0 <= N <= 500,000
  • 채널은 0부터 무한대까지 => - channel은 1,000,000 까지 훑기 - ex) - n = 500,000 / 가능한 버튼: 8 1. 100 -> 500,000 : [499,900 번] 2. 888,888 -> 500,000 : [388,888 번] - 밑에서 목표값까지 ++보다 위에서 목표값으로 – 가 더 빠를수도 있음 (1,000,000은 적당히 큰 값을 그냥 넣은 것)
import sys
input = sys.stdin.readline

n = int(input())
_ = int(input())
# 정상 작동하는 버튼의 집합
btns = tuple(map(int, input().split()))

# 최솟값 초기값: 100에서 목표 채널까지 이동한 수
min_count = abs(100 - n)

# 모든 경우의 수 탐색
for channel in range(1000001):
    channel = str(channel)
    flag = 0
    for ch in channel:
        # 고장난 버튼이 있다면 break
        if int(ch) in btns:
            flag = 1
            break
    # 정상 작동한 버튼으로 만들어진 채널인 경우
    # 최솟값 비교
    if flag == 0:
        min_count = min(min_count, abs(int(channel) - n) + len(channel))

print(min_count)