[CodingTest] BOJ1107 리모컨 ( 브루트포스 ) With 파이썬

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

1107번: 리모컨

 

◎ 문제풀이 

 

채널을 이동하는 경우는 2가지가 있다.

 

첫번째 경우 : 100번에서 +,-로 이동하는 경우

두번째 경우 : 리모컨 버튼으로 목표채널과 가장 가까운 채널로 이동 후 +,-로 이동하는 경우

 

두 가지 경우 중 최솟값이 정답이다.

 

두번째 경우는 브루트포스로 풀어야 한다.

브루트포스는 탐색할 범위를 먼저 정해야 한다. 채널은 0~500,000 까지 있지만 리모컨은 9999...9999 무한대로 눌릴 수 있다. 500,000 채널을 탐색하는데 480,000보다 500,001이 더 빠르다. 그러므로 범위는 500,000의 2배인 1,000,000로 정한다. 즉, 0~1,000,000 사이의 수 중 목표와의 거리가 최소인 수를 구하면 된다.( 단, 고장난 버튼이 포함된 수는 제외한다. ) 

 

 

◎ 코드

import sys
input = sys.stdin.readline
target = int(input())
n = int(input())
broken = list(input().split())
  
ans = abs(target-100)

for x in range(1000001) :
  now = str(x)
  for i in range(len(now)) :
    if now[i] in broken : break
    if i == len(now)-1 :
      ans = min(ans,abs(target-int(now))+len(now))
      
print(ans)

 

 

시간제한 1초는 대략 1억~2억번의 연산횟수를 의미한다. 위 코드는 이중for문이고 시간복잡도는 O(1,000,001X6)이다. 대략 600만번의 연산횟수이므로 브루트포스 풀이로 충분하다. 

 

나는 브루트포스가 아닌 '구현'으로 어떻게든 목표와 가장 근사인 값을 찾으려고 했다. 하지만 고장난 버튼이 존재하여 구현이 어려웠다. 가장 단순한 방법을 먼저 생각하고 시간복잡도를 빠르게 계산하는 것이 중요하다. 시간 안에 가능하다고 판단되면 가능한 단순한 풀이로 풀어야 한다.