[백준/Python] #1107번 리모컨

 

문제 

• 리모컨 0~9 숫자, +, -
• 현재 채널 100, 채널 N까지 이동하기 위해 버튼(+, -)을 최소 몇 번 눌러야 할까?
• 단, 0에서 - 버튼을 누르면 동작 X, 채널은 무한대 만큼 있음

 

입력

1. 채널 N (0 ≤ N ≤ 500,000)
2. 고장난 버튼의 개수 M (0 ≤ M ≤ 10)
3. 고장난 버튼

5457
3
6 7 8

 

출력

채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지

6

 

 

정답

import sys
input = sys.stdin.readline

def remote_controller(N, M, buttons):
    min_cnt = abs(100 - N)
    
    if N == 100:
        return 0 
    for i in range(1000001):
        for t in str(i):
            if t in buttons:
                break
        else:
            min_cnt = min(len(str(i)) + abs(N - i), min_cnt)
    return min_cnt

if __name__ == "__main__":
    N = int(input())
    M = int(input())
    if M > 0:
        buttons = input().split()  # 고장난 버튼 목록
    else:
        buttons = []
    
    print(remote_controller(N, M, buttons))

 

해결 아이디어

• 입력은 M이 0인 경우 button를 받으려고 하면 컴파일 에러가 나기 때문에 M이 0일 때와 0보다 클 때를 나눠서 따로 처리해 줬다.
• 처음 최솟값은 현재 채널(100)에서 +와 -만을 사용하여 채널을 이동하는 경우(`abs(100-목표 채널`))로 설정해 줬고, 목표 채널이 100이라면 움직일 필요가 없으므로 바로 0을 return 하도록 했다.
• 0~1,000,000까지 숫자를 하나씩 탐색하며 각 숫자의 자릿수마다 고장 난 버튼의 목록에 있는지 확인하여 전체 자릿수가 목록에 있다면 넘어가고 목록에 없다면 최솟값을 저장하는 변수(`min_cnt`)와 비교하여 최솟값을 업데이트하도록 했다. 
• N의 범위는 0~500,000이지만 버튼은 +, -가 있고 특정 채널에서 증가하는 경우 일 수도 있고, 감소하는 경우 일 수도 있으므로 0~1,000,000 범위를 고려해서 풀어줘야 한다.