[백준/BOJ] - 1107번 python 풀이 - 브루트포스

---

처음 나의 풀이법

 

문제를 보고 처음 떠오른 방법이 가능한 숫자를 가지고 목표 채널에 근접하는 방법.

만약 목표 채널이 5457이라면 일단 각 자릿수가 일치하는지 먼저 확인, 일치 하지 않다면 절댓값 1만큼 차이나게 수를

뽑으며 각 자리수 별로 가능한 경우의 수 집합을 만든다.(5457의 맨 첫자리인 5를 기준으로 4 or 6이 있다면 4와6을 set에 집어 넣는다.) 이런식으로 하면 집합이 자릿수 개수 만큼 총 4가지가 생길 것이다. 해당 집합에서 하나씩 값을 골라 순열을 진행하는 방식으로 하면 될거라 생각했으나 순열은 같은 수를 여러번 뽑는 경우를 생각하지 못한다.

 

최종 풀이법

 

그렇기에 다른 분의 풀이를 참고하여 브루트포스 방식으로 모든 경우의 수를 훑는다.

코드 부분에 반복 횟수가 1,000,001로 되어있는 이유는 주어질 수 있는 target의 맥시멈은 500,000이고 만약 0부터 8까지 고장났다고 가정하면 100 -> 500,000 경우와 999,999 - 500,000를 비교. 사실상 100 -> 500,000을 +-로 움직이는게 가장 맥시멈한 값일 것이다. 499,900 그렇다면 확인해야하는 경우는 100 ~ (500,000 + 499,900) 즉 100부터 999,900까지 확인을 해야한다. 그래서 여유분을 남기기 위해 반복횟수를 10만 이상으로 설정한 것.

 

결론

 

결론적으로 0부터 1,000,000까지 num만큼 고장나지 않은 리모컨 버튼으로 바로 이동할 수 있는지를 확인한다.

이동할 수 있다면 해당 번호의 길이만큼의 수와 타겟 넘버와의 절댓값 차이를 더하여 얼마만큼의 버튼을 눌러야하는지 계산하며, 현재까지의 버튼 누르기 최솟값과 비교하여 더 작은 값을 도출한다. 모든 반복이 끝나면 정답이 나온다.

---

import sys
input = sys.stdin.readline

target = int(input())
n = int(input())
break_btn  = list(map(str,input().split()))
mini = abs(target - 100)

for num in range(1000001):
    str_num = str(num) #문자로 치환하여 비교
    length = len(str_num)
    for i in range(length):
        if str_num[i] in break_btn: #idx를 통해 망가진 버튼인지 확인
            break
        if i == length-1:
            mini = min(mini, abs(target - num) + length)
print(mini)

---