[백준] 1107번 : 리모컨

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

1107번: 리모컨

리모컨의 버튼을 눌러야하는 횟수를 계산해야하는 문제이다. 고장난 버튼이 있는데 고장난 버튼을 누르지 못한다.

고장난 버튼을 누르지않고 100번에서 N번까지 리모컨을 눌러야하는 최소 횟수를 구하는 문제이다.

처음에는 그리디 방식으로 접근을 하였습니다. N과 최대한 가까운수를 구하는 방법을 찾기 시작하였고 다음  테스트 케이스 반례로 그리디 문제로 해결 할 수 없다는것을 알게 되었습니다.

1555

8

0 1 3 4 5 6 7 9

100에서 1555로 가야하는 최소 리모컨 누르는 횟수를 구해야한다. 사용 할 수 있는 버튼은 2,8,+,- 이다.

1) + 로만 버튼을 눌렀을때 값 : 1555-100 = 1455

2) 숫자버튼을 누른뒤 + 혹은 - 눌렀을때의 값 ( 목표로하는 숫자에서 가장 가까운 수를 선택한다): 

 - 1와 최대한 가까운 수 선택 : 2

 - 5와 최대한 가까운수 선택 : 2

 - 5와 최대한 가까운수 선택 : 2

 - 5와 최대한 가까운수 선택 : 2

 -> 4 + 667 = 671

1와 2의 최소값을 구하여 리턴한다 671

 

반례)

888 번호를 선택

-> 3+ 667 = 670번

 

-> 더욱 복잡한 수학적 로직이 필요하다 ( 그리디 방식으로 풀 수 는 있으나 너무 복잡함 )

 

따라서 0 부터 50000 까지 모든 경우의 수를 탐색해본다.

def is_possible_channel(channel):
    if channel == 0:
        return 0 not in brokennumber

    while channel > 0:
        digit = channel % 10
        if digit in brokennumber:
            return False
        channel //= 10

    return True

def find_nearest_channel(target):
    min_push = abs(target - 100)  # 100에서 +, - 버튼으로만 이동하는 경우의 횟수

    for channel in range(500001):
        if is_possible_channel(channel):
            press_count = abs(target - channel) + len(str(channel))
            min_push = min(min_push, press_count)

    return min_push

N = int(input())  # 목표 채널
M = int(input())  # 고장난 버튼 개수
brokennumber = []
if M > 0:
    brokennumber = list(map(int, input().split()))  # 고장난 버튼 리스트

print(find_nearest_channel(N))