[탐색/Brute Force] 백준 1107 리모컨 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1107번: 리모컨

 

 

 

2. 문제 풀이

 100번에서 원하는 채널(N)로 전환하기위해 리모컨 버튼을 눌러야 합니다. 위아래로 이동할 수 있는 화살표와 0~9번까지의 버튼이 있습니다. 이 중 숫자버튼 일부가 고장났을 때, 눌러야 할 버튼의 최소 횟수를 구하는 문제입니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 기본 로직은 이렇습니다. 최대한 목표 채널에 가까운 채널로 이동한 뒤, 위아래(+1/-1)로 이동하면 최소 횟수로 목표 채널로 갈 수 있습니다. 다만, '목표 채널에 가까운 채널'을 찾는 게 어렵습니다. 차라리 1~50000번까지 완전탐색하는 게 더 빠릅니다.

 

 

 

3. 코드

from itertools import product

#입력
N = int(input()) #목표 채널
M = int(input())
number = list(range(10))
if M > 0:
    broken = set(map(int, input().split())) #고장난 숫자버튼
    number = list(set(range(10)) - broken) #고장나지 않은 숫자버튼

case = list(product(number, repeat=len(str(N))))
res = 500000 #최대 이동수
for c in case:
    num = 0
    for i in c:
        num *= 10
        num += i
    res = min(res, abs(N-num)+len(str(num)))

#100번에서 이동한 것과 비교
print(abs(N-100) if abs(N-100) < res else res)

 맨 처음에는 고장나지 않은 숫자버튼으로만 중복순열을 구성해서 'N과 가장 근접한 채널'을 찾았습니다. 예제 입력은 모두 통과하나, 아래와 같은 예외가 존재합니다.

 

 

9
9
0 2 3 4 5 6 7 8 9

output: 9 (1->+8)
Answer: 4 (11->-2)

 쓸 수 있는 숫자가 1밖에 없을 때, 9로 가기위한 최선의 방법은 11로 이동한 후 2칸 내리는 것입니다. 하지만 중복순열의 길이를 1의 자리(N=9)로 해뒀기 때문에 찾지 못합니다. 이를 해결하기 위해서는 repeat의 개수를 여유롭게 len(str(N))+1로 해줘야 합니다.

 

 

500000
8
0 2 3 4 6 7 8 9

Output: 499900
Answer: 11117

 하지만 이 경우에는 0을 사용할 수 없을 때, 빈 앞 자리를 0으로 채우지 못해 오류가 발생합니다.

 

 

#입력
N = int(input()) #목표 채널
M = int(input())
broken = []
if M:
    broken = list(input().split()) #고장난 숫자버튼

res = abs(100 - N) #100번에서 +/-로만 이동할 때, 필요한 버튼 수
for channel in range(999900):
    #고장난 버튼이 포함되어있으면 넘어가기
    for i in str(channel):
        if i in broken:
            break

    #고장난 버튼이 없으면 계산
    #[채널이동에 필요한 버튼 횟수]와 [+/-버튼 누를 횟수]를 계산해서 비교
    else:
        res = min(res, len(str(channel)) + abs(N - channel))
print(res)

 차라리 모든 경우의 수를 고려해서 찾는 게 더 간단합니다. 수빈이가 이동하려는 채널의 범위는 (0 ~ 500000)까지지만, 전체 채널의 범위는 0부터 무한대까지입니다. (문제 조건)

 따라서 큰 수에서 작은 수로 내려오는 경우의 수도 생각해야 합니다. 최악의 경우는 N이 500000이고 100번에서 +하는 횟수입니다. (499900회) 이를 더해서 상한을 정해줍니다. 즉, 999900에서 500000까지 내려오는 최악의 경우를 상정해서 범위를 제한합니다.