[백준, 브루트포스] 1107_리모콘

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

1107번: 리모컨

 

사용가능한 숫자들에 대한 조합들 중 목표하는 값간의 차가 가장 작은 숫자를 구하는 방식으로 풀려했지만 실패했다.

정확하게 어떻게 풀어야할지 감을 못 찾아서 다른 분의 풀이를 참고했다..

 

다른 분들의 코드를 보니 모든 경우를 탐색하는 브루트포스 알고리즘으로 푼 것을 알 수 있었다.

 

과정

• 결국 최악의 경우는 1로만 이동하는 경우
• 사용가능한 숫자만 사용해 숫자를 만든 경우, 최솟값을 검사하고 업데이트하기

의문점

• 완전 탐색의 범위를 (목표값 * 2 + 1) 로 생각하고 풀었지만 틀렸다.
• 최대값이 500,000 이기에 1,000,000까지 사용가능하도록 해야 정답이지만 아직 이해가 잘 되지는 않는다.

 

코드

import sys
input = sys.stdin.readline

goal = int(input())
current = 100
count = abs(100 - goal) # 처음부터 1로만 위 아래 처리할때 값을 기본
numset = set()
num = int(input()) # 사용 불가 갯수

if num != 0:
    numset = set(map(str, input().split()))
    # str로 읽어서 set의 key로 설정
else:
    numset = set()

if goal == 100:
    print(0)
    exit(0)

for i in range(1000001): # goal * 2 +1
    current_set = str(i)
    if len(numset & set(current_set)) != 0: # 사용 불가숫자랑 곂치는 게 있으면
        continue
    else:
        count = min(count, abs(goal - i) + len(str(i)))
        # abs(goal - i) : 목표값이랑 1씩 증감 count 수
        # len(i) : i 길이만큼 눌러줘야하는 숫자 횟수

print(count)