[Python] 1107번 리모컨

 

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

1107번: 리모컨

 

---

 

22/12/04

 

 

조금 생각해야되는 브루트 포스 문제로, 조금만 생각한다면 그리디 알고리즘으로도 풀 수 있을 것 같다.

---

 

문제 접근 방식:

 

 

이 문제는 두가지 방법으로 풀 수 있다.

 

어떻게 하면 최소버튼을 누르게 만드는 번호를 찾을 수 있을까?로 접근한다면 그리디적인 접근으로 푸는 것이고, 그냥 생각 없이 채널 번호를 $0$부터 $1,000,000$까지 확인하면서 돌리면 브루트 포스로 푸는 것이다.

 

나는 처음에 그리디적인 접근을 하려고 했으나, 좀 귀찮아서 시간제한과 범위를 보고 브루트 포스 풀이가 가능하다고 판단하여 브루트 포스 풀이로 진행했다.

 

 

브루트 포스 풀이는 다음과 같다.

 

먼저 리모컨을 눌러서 나올 수 있는 채널번호를 $0$번부터 $1,000,000$번까지 확인하면서, 그 번호가 고장나지 않은 버튼으로 누를 수 있는지를 확인한다.

 

고장 나지 않은 버튼으로 누를 수 있는지 확인이 된다면, 그 번호에서 우리가 보고 싶은 번호까지 $+$버튼 또는 $-$버튼을 이용해서 이동하는 것이라고 생각하면 된다.

 

그래서 (그 채널 번호의 길이) + (그 번호에서 우리가 보고싶은 번호까지 $+$버튼 또는 $-$버튼 만을 이용하여 이동하는 횟수)가 그 채널 번호에서 우리가 보고 싶은 번호까지 갈 수 있는 최소의 버튼 누름 수이다.

 

예를 들어, 예제 입력 3의 상황을 보자.

500000
8
0 2 3 4 6 7 8 9

이 경우, 답이 $11117$이 나오는데, 그 이유는 처음에 $511111$으로 가고($6$번 누름), 이후 $-$버튼만 눌러서 $500000$으로 갔기 때문이다.($11111$번 누름)

 

다시 말해, 처음에 버튼만을 눌러서 갈 수 있는 숫자를 $0$번부터 $1,000,000$번까지 탐색하는 것이라고 생각하면 된다.

 

 

그리디적인 풀이는 처음에 버튼만을 눌러서 갈 수 있는 숫자를 목표숫자와 가장 가깝게 하도록 버튼만을 눌러서 갈 수 있는 숫자를 구성하고, 이후 바로 최솟값을 찾는 풀이로 생각된다.

 

단지 목표숫자와 가장 가깝게 하도록 숫자를 구성하는 것이 까다로울 뿐이다.

 

 

그리디적인 풀이나 브루트 포스 풀이나 공통점은, $100$번에서 시작한다는 점을 주의해야 된다는 것이다.

 

때문에 최소 시간은 적어도 $|end - 100|$이 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1107번 리모컨
# 브루트포스
'''
접근 방법:
어차피 정상 버튼은 최대 10개이고, 이동하려는 채널 번호는 최대 50만이기 때문에
100만번 반복해서 돌면 끝임
'''
import sys
N = int(input())
M = int(input())
if M == 0:
    broken_button = set()
else:
    broken_button = set(input().split())
start = 100
min_time = abs(N-start)  # 최소 몇번 눌러야 하는지
for i in range(1000001):
    is_normal_can_go = True  # 정상버튼만 눌러서 갈 수 있는지
    for j in str(i):
        if j in broken_button:
            is_normal_can_go = False
            break
    if is_normal_can_go:
        time = len(str(i)) + abs(N-i)
        if time < min_time:
            min_time = time
print(min_time)