졍's 기술 블로그

리모컨

티어 : Gold 5
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제 입출력

힌트

예제 1의 경우 5455++ 또는 5459--

Algorithm

완전 탐색 이용
1. 고장난 버튼을 제거하고 찾는 채널과 가장 가까운 수 만들기
2. 해당 숫자의 자리수 + (찾는 채널 - 만든 수) Return

고려해야 할 조건들이 너무 많아 힘들었던 문제 ㅠㅠ

Code

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
error_key = []
if M > 0:
    error_key = list(map(int, input().split()))
# 사용 가능한 키는 True, 그렇지 않으면 False
error_keys = dict()
for i in range(10):
    if i not in error_key:
        error_keys[i] = True
    else:
        error_keys[i] = False

# 보고싶은 채널과 가장 가까운 숫자 만들기
one_step = 5000011
# 찾는 채널보다 작은 수로 가까운 숫자 만들기
for num in range(N, -1, -1):
    # 찾는 채널이 100이거나 M이 0이거나 숫자가 모두 고장이면 break
    if N == 100 or M == 0 or M == 10:
        break
    
    # keys 중 error_key에 없는 숫자를 이용해 해당 숫자 만들 수 있으면 break
    temp = list(str(num))
    # error_key가 아닌 key 개수 세기
    count = 0
    for i in temp:
        if error_keys[int(i)]:
            count += 1
    # count가 temp의 길이와 같으면 만들 수 있는 숫자
    if count == len(temp):
        one_step = num
        break

# 찾는 채널보다 큰 수로 가까운 숫자 만들기
num = N
while True:
    # 찾는 채널이 100이거나 M이 0이거나 숫자가 모두 고장이면 break
    if N == 100 or M == 0 or M == 10:
        break
    
    # keys 중 error_key에 없는 숫자를 이용해 해당 숫자 만들 수 있으면 break
    temp = list(str(num))
    # error_key가 아닌 key 개수 세기
    count = 0
    for i in temp:
        if error_keys[int(i)]:
            count += 1
    # count가 temp의 길이와 같으면 만들 수 있는 숫자
    if count == len(temp):
        # 찾는 채널보다 작은 채널의 숫자 차이가 작으면 갱신
        if one_step < N:
            if N - one_step > num - N:
                one_step = num
                break
        else:
            one_step = num
            break
    
    if one_step < N and num - N >= N - one_step:
        break
    num += 1

answer = 0
if N != 100:
    if M == 10 or one_step == 5000011:
        if M == 0:
            answer = min(max(100-N, N-100), len(str(N)))
        else:
            answer = max(N - 100, 100-N)
    # 100에서 +와 -만을 이용해 움직인 횟수가 one_step과의 차이보다 작으면 갱신
    elif max(100-N, N-100) < max(N-one_step, one_step-N) + len(str(N)):
        if one_step == 5000011:
            answer = min(max(100-N, N-100), len(str(N)))
        else:
            answer = max(100-N, N-100)
    # 숫자 중 고장난 키가 하나도 없으면 채널 번호 길이만큼 출력
    elif M == 0:
        answer = len(str(N))
    else:
        answer = len(str(one_step))
        answer += max(N - one_step, one_step - N)
print(str(answer))

메모리: 30864 KB
시간: 2004 ms