iamyoungbin

You’ll never forget my name

1 분 소요

Problem

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

Idea

주어지는 목표 채널의 범위가 0~500000 이므로 목표 채널과 거리를 비교해보아야 하는 채널의 범위는 0~100000이 된다. 채널을 찾기 위한 연산의 횟수가 100만번으로 충분히 작으므로 브루트 포스를 이용하여 풀이하였다.

우선, 시작 채널이 100이므로 해답의 초기 값을 100부터 목표 채널까지의 거리로 설정하였다. 반복문을 통해 0~100000의 범위 내의 채널으로부터 목표 채널을 만드는 클릭 횟수를 계산했다. 이 때, 만든 채널의 숫자 중에 고장난 버튼이 포함되어 있을 경우 제외했다. 채널을 만들 수 있을 경우 기존 해답 값과 비교하여 작은 쪽으로 갱신했는데, 최종적으로 목표 채널로 이동하기 위한 값은 (해당 채널을 만드는 클릭 횟수) + (해당 채널로부터 목표 채널로 이동하기 위한 클릭 횟수) 이다.

Code

import sys

input = sys.stdin.readline

N = int(input())
M = int(input())
broken = list(map(int, input().split()))

sol = abs(100 - N)
for num in range(1000001):
    str_num = str(num)
    for i in str_num:
        if int(i) in broken:
            break
        
    else:
        sol = min(sol, len(str_num) + abs(num - N))
        
print(sol)

Comment

문제를 보자마자 브루트 포스로 해결해야된다고 직감하고 다음을 비교하여 해답을 구하려 했다.

  1. 100에서부터 목표 채널을 만드는 방법
  2. 목표 채널보다 한 자리 낮은 수 중 만들 수 있는 가장 큰 수 중에서 목표 채널을 만드는 방법
  3. 목표 채널에서 한 자리 높은 수 중 만들 수 있는 가장 작은 수 중에서 목표 채널을 만드는 방법
  4. 목표 채널과 같은 자리 수 중에서 가장 가까운 수에서 목표 채널을 만드는 방법

이러한 방법으로 해답을 구하려다가 아무리 생각해도 올바른 방법이 아닌 것 같아 다른 사람들의 풀이를 찾아보게 되었는데 단순한 접근법으로 더 쉬운 풀이가 가능해져 놀랍기도 실망스럽기도 했다. 좀 더 심플하게 생각하자.

참고