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

solved.ac 난이도 :  GOLD5

백준  1107번- 파이썬 풀이

 

<문제>

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

1107번: 리모컨

<풀이>-완전탐색,브루트포스 알고리즘

채널 N의 범위가 0<=N<=50,000이라고 했으므로 고장나지 않은 숫자중에 만들수 있는 모든 숫자를 살펴보면서 N과 가장 차이가 적은 번호를 찾으면 된다.

 

이를 위해 버튼을 누를 수 있는 최대 번호를 100,0000으로 한다.

 

1,000,000으로 하는 이유는누를 수 있는 번호가 500,000보다 클 수 있기때문에 500,000보다 크면서 모든 숫자를 다 거칠 수 있는 숫자이기 때문이다.

 

따라서 1~1,000,000까지의 숫자를 반복문을 통해 살펴본다.

 

각각의 숫자를 문자열로 변환후 문자열에 누를 수 없는 버튼이 있다면 다음 번호로 넘어간다.

 

현재 살펴보고 있는 숫자에 누를 수 없는 버튼이 없다면 현재 숫자에서 N을 뺀 절댓값을 구한다.(채널입력후 목표채널로 가기위한 +,-의 크기)

 

위에서 구한 절댓값에 누른번호의 길이(버튼 누른 횟수)를 더해야 최종적으로 버튼을 누른 횟수를 구할 수 있다.

 

반복문을 통해 현재 살펴보고 있는 숫자와 100(현재 보고 있는 채널)을 뺀후 절댓값을 구해 위에서 구한값과 비교한다.->더 작은값 선택

 

각각의 경우에서 위 과정을 반복해 최솟값이 나올때마다 그 값을 갱신해준다.

<코드>-파이썬

import sys
input = sys.stdin.readline
target = int(input())
n = int(input())
break_num= 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 break_num:
            break

        # 고장난 숫자 없이 마지막 자리까지 왔다면 min_count 비교 후 업데이트
        elif j == len(nums) - 1:
            min_count = min(min_count, abs(int(nums) - target) + len(nums))#(min_count,현재채널에서 목표채널로 가기위한 버튼 클릭 횟수)

print(min_count)