[백준] 1107번 리모컨 - 파이썬(Python)

문제 (링크)

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

1107번: 리모컨

 

나의 풀이

import sys
input = sys.stdin.readline
target = int(input())
n = int(input())
broken = list(map(int, input().split()))

# 현재 채널에서 + 혹은 -만 사용하여 이동하는 경우
min_count = abs(100 - target)

for nums in range(1000001):
    nums = str(nums)
    
    for j in range(len(nums)):
        # 각 숫자가 고장났는지 확인 후, 고장 났으면 break
        if int(nums[j]) in broken:
            break

        # 고장난 숫자 없이 마지막 자리까지 왔다면 min_count 비교 후 업데이트
        elif j == len(nums) - 1:
            min_count = min(min_count, abs(int(nums) - target) + len(nums))

print(min_count)

풀이법 및 코드 설명

브루트포스 방식으로 모든 경우의 수를 탐색한다.

 

처음에는 고장나지 않은 숫자들로 만들 수 있는 모든 순열을 만들어주고, target과 가장 가까운 순열을 구해 두 숫자 사이의 차이를 구하고자 했다.

 

하지만, 순열을 만드는 과정에서 요소를 중복해서 뽑을 수 있어야하기 때문에 (Ex ) 5555 등..) 기존에 알고 있던 itertools.permutations를 사용할 수 없었다.

 

따라서, 모든 가능한 수에 대하여 해당 작업을 처리해주었다.

 

여기서 range를 N의 최대 범위인 500,000이 아닌 그 두 배 1,000,000로 해준 것은, 수빈이가 이동하려는 채널의 범위는 500,000 이하이지만 채널 자체는 무한대라는 점 때문이다.

 

따라서, target와 가장 가까운 숫자를 찾을 때 target보다 작은 값은 물론이고 target보다 큰 값도 찾아줘야하고, 이 값은 500,000 이상도 가능하다.

 

만약에 수빈이가 이동하려는 채널이 500,000이고, 리모컨의 숫자 중 1, 2, 3, 4, 5가 고장났다고 가정하자.

 

이 때, range의 범위가 500,000으로 제한되면, 시작점인 100번에서 +만 눌러서 500,000까지 도달하는 총 499,900번 버튼을 클릭하게 할 것이다.

 

하지만 물론 이것은 최적의 해가 아니다.

 

600,000에서 -를 100,000번 눌러 target에 도달하는 것이 최적의 해일 것이다.

 

이러한 이유 때문에 range는 1,000,000까지로 설정해주어야 한다.