[백준 - Python] 1107. 리모컨 (완전 탐색)

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

1107번: 리모컨

 

코드

import sys
input = sys.stdin.readline

target = int(input())
n = int(input())
broken = list(map(str, input().split()))

min_count = abs(100 - target)
for nums in range(1000001):
    nums = str(nums)  # 숫자의 각 자리 수를 수월하게 확인하기 위해 문자열로 변환

    for idx, n in enumerate(nums):
        if n in broken:
            break
        elif idx == len(nums) - 1:
            min_count = min(min_count, abs(int(nums) - target) + len(nums))

print(min_count)

 

목표 채널을 target 변수에 저장하고

고장난 버튼의 개수는 n에 저장하고

고장난 버튼 리스트는 broken에 저장한다

 

최소 카운트를 구해야 함으로

최소 카운트 저장할 변수를 최대 카운트 횟수인 abs(100-target)으로 초기화 해준다

 

이 문제의 핵심 아이디어는

우선 목표하는 숫자와 가장 가까운 숫자를 숫자 버튼을 이용해 누른 다음에

목표 숫자까지 눌러야 하는 + 혹은 - 개수를 누른 숫자 버튼의 개수에 더해주면

답을 구할 수 있다는 점이다

 

가장 가까운 숫자를 특별한 아이디어로 구하는 것이 아니라

1부터 1000000까지 순차적으로 확인하면서 최소 카운트를 구한다는 점에서 완전 탐색 문제라고 볼 수 있다

 

일정한 범위를 돌면서

분기문으로 간단하게 문제에서 주어진 조건을 만족하는지

확인하는 코드를 짤 수 있어야 한다.

 

완전 탐색이라는 아이디어를 떠올렸으면,

구현 문제라는 생각이 들기도 한다.

 

채널 N의 최대 값이 500,000인데 1000000까지 탐색을 하는 이유는

목표 채널보다 큰 수에서 - 버튼을 이용해 내려오는 방식에

최소 카운팅이 가능할 수도 있기 때문이다.

 

순차적으로 탐색을 하면서

숫자 중에 망가진 버튼이 있다면 다른 숫자로 이동하고

만약 고장난 숫자 없이 마지막 자리수까지 온 경우에

최소 카운트를 저장하는 변수인 min_count를 업데이트 해준다

 

이때, 아까 위에서 말한(밑줄 쳐진 부분) 내용을 min 함수의 인자로 넣어주어서

현재 저장되어 있는 값보다 작을 때에만 업데이트를 진행한다

 

1부터 차례대로 가능한 경우를 완전 탐색하며 해답을 찾아야 한다는 생각과 더불어

떠올린 아이디어를 코드로 구현할 줄 알았어야 풀 수 있는 문제였다

 

 

최소값을 저장하는 변수에 가능한 최대값을 저장한 후에,

min 함수를 통해 업데이트 해 나가는 방식이라던지

 

반복문을 돌기 위해 숫자를 문자열로 바꿨다가,

정수 리스트에 포함되는지 확인하기 위해 숫자로 바꾸는 방식이라던지

 

마지막 자리수까지 왔는지 확인하기 위해 인덱스가 (숫자의 길이 - 1)인지 확인한다던지

 

하나씩 살펴보면 별 거 없어보이지만

이 모든 것을 주어진 시간 내에 떠올리고 구현할 수 있어야 한다는 점에서 아직 많은 연습이 필요해 보인다 !!!