[백준/python] 1107번: 리모컨

문제

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

1107번: 리모컨

---

문제 요약

이동하려는 채널과 고장난 버튼들을 입력 받고, 해당 채널로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지 출력한다.

+ 현재 채널은 100번이다.

---

코드

import sys
input = __import__('sys').stdin.readline

N = int(input()) # 이동하려는 채널
M = int(input()) # 고장난 버튼 개수

broken = list(map(int, input().rstrip().split()))

min_cnt = abs(100 - N)
# 현재 채널 100번에서 + 또는 - 만 사용하여 이동하는 경우

# 이 반복문은 숫자 버튼을 통해 num을 거쳐서 원하는 채널로 이동하는 경우를 체크한다.
for num in range(1000001):
# 채널은 무한대이기 때문에 500000이 최대가 아님
    num = str(num)
    for i in range(len(num)):
        if int(num[i]) in broken:
        # 고장난 숫자가 있으면 break
            break
        elif i == len(num) - 1:
        # 고장난 숫자 없이 마지막 자리까지 왔다면 (num이 리모콘으로 직접 입력 가능한 숫자인 경우)
            min_cnt = min(min_cnt, abs(int(num) - N) + len(num))
            # 채널 num과 목표 채널과의 차이(+, -로 움직일 횟수) + num의 길이(num으로 이동할 때 버튼을 누를 횟수)
            # 이전 최소 횟수와 비교하여 업데이트
print(min_cnt)

---

코드 설명

1.  최악의 상황은 리모콘의 리모콘의 모든 숫자 버튼이 고장난 상황이다.

(현재 채널에서 +, - 버튼만 사용하여 원하는 채널 N으로 이동해야한다.)

=> 결과 값 min_cnt을 일단 (100 - N)의 절댓값으로 설정한다. (절댓값은 N이 100보다 큰 상황 고려)

 

2. 모든 채널 0부터 1000001까지 직접 하나씩 체크하며 min_cnt값을 업데이트 시켜준다.

(이동하려는 채널의 수는 0부터 500000까지 이지만, 전체 채널의 수는 무한대이므로)

+ 이 반복문은 숫자 버튼을 통해 num을 거쳐서 원하는 채널로 이동하는 경우를 체크한다.

 

3. 체크한 채널의 모든 자릿수에 고장난 숫자가 없다면 (리모콘으로 직접 입력 가능한 숫자인 경우)

 

3-1.  min 함수를 통해 이전까지 가장 최소 입력 횟수 min_cnt와 비교하여 업데이트한다.

 

++ 목표 채널과 체크하고 있는 채널의 차이 (+, - 버튼으로 움직일 횟수) + 체크하고 있는 채널의 자릿수 (숫자 버튼을 누를 횟수)가 체크한 채널을 거쳐서 원하는 채널로 이동할 때 최소한 눌러야하는 버튼 횟수이다.