백준 1107 리모콘(Brute-Force)

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

1107번: 리모컨

브루트포스

즉, 완전탐색 문제를 만나면 변수의 범위를 확인해서 전체의 경우를 고려해줄 필요가 있다.

문제를 이해하기에는 크게 어렵지 않았다. 

1. 시작 채널이 100번이라고 했으니까 목표 채널 N까지 ++,--만 누르는 abs(100 - N) 경우

2. N을 모두 누를 수 있는 경우

3. N과 가장 가까운 숫자에서 ++,--를 누르는 경우

 

모든 경우를 확인해야 하기 때문에 2,3을 묶어서 생각할 수 있는데

문제에서 N은 최대 500,000이기 때문에 for의 범위를 500,000으로 생각할 수 있지만

N은 정답을 구하는것이고 우리는 어떤 temp의 채널에서 N에 맞춰서 구해야 하기 때문에

정확하게 지금 for문의 범위는 N의 범위가 아닌 temp의 범위를 설정해야한다.

 

가장 많은 경우가 드는 경우는 ++,--만 누르는 것인데

N이 최대 500,000이니까 1,000,000에서 --를 50만번 누르는 경우가 가장 큰 경우다. 

즉 temp는 0 ~ 1,000,000에서 완전 탐색을 진행한다

(가장 최소의 경우를 구하는 것이기 때문에 ++했다가 --를 하는 의미없는 짓은 고려하지 않아야 하기 때문)

N = int(input())
M = int(input())
if M:
    broken = set(input().split())
else:
    broken = set()

ans = abs(100 - N) # ++ or -- 로 이동할 경우 -> 최댓값

# 작은수에서 큰수로 이동할땐 500,000 까지만 보면 되지만
# 반대로 큰수에서 작은수로 내려올수도 있으므로 1,000,000 까지 봐야함
# n이 500,000일 때
# 0에서 ++ 50만번, 1,000,000에서 -- 50만번 누를 수 있는 경우가 있기 때문에
# 1,000,000까지 모두 고려해줘야 한다

for num in range(1000001):
    for temp in str(num):
        if temp in broken: # 해당 숫자가 번호를 눌러서 만들 수 없는 경우엔 스탑
            break
    else: # 번호를 눌러서 만들 수 있는 경우엔
    	# min(기존답, 번호를 누른 횟수 + 해당 번호로부터 타겟까지의 차이)
        #print(num)
        ans = min(ans, len(str(num)) + abs(num - N))

print(ans)