1107 - 리모컨

아니, 왜 플레 문제보다, 요게 더 어려운거 같지 ;;

 

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

1107번: 리모컨

 

해당 문제인데요. 진짜 몰라서 결국 아이디어를 참고했는데, 그래도 어안이 벙벙하군요.

 

1. 처음엔 100에서 BFS로 접근을 해봤습니다.

 

예제부터 뭔가 너무 오래걸려서 이건 아니겠다 싶어 다른 방법 생각..

 

2. 채널의 자릿수를 비교해가면서, 최적의 값을 만들어내면 되지 않을까 싶어 주어진 목표 채널 1의 자리부터 비교하여, 최적의 값을 비교하려 했죠.

 

근데, 이것도 엣지 케이스를 커버할 수 있는 코드가 되지 못함

 

음..

 

그래서, 포기하고 좀 찾아보니, 답을 미리 정해놓고 최소값을 정하는 방법이라길래.

 

아 설마

 

 

해서 좀 짜보니 답이 맞네요.

 

왜 이 문제가 브루트 포스인지 알게되는 순간..

 

약간 기업에서 코딩테스트를 치를 때, 자주 내는 문제의 타입이 아닌가 싶습니다.

 

엣지 케이스도 많고, 구현 능력 보는 문제라

---

import sys

input = sys.stdin.readline

N = int(input())
M = int(input())
ARR = list(map(int, input().split())) if M else []

R = [1] * 10
for i in ARR: R[i] = 0

C = abs(N - 100)
for i in range(1000000):
    for j in str(i):
        t = int(j)
        if not R[t]:
            break
    else:
        C = min(C, abs(N - i) + len(str(i)))
  
print(C)

---

저녁 먹기전에 가볍게 풀고 밥 먹으려 했는데 ..

 

입 맛만 버렸넹 ㅠㅠ

 

이상 1107 - 리모컨였습니다.