[백준 1107] 리모컨
1107번 : 리모컨
방법 1 (틀림)
-
내가 생각한 방법
-
목표 숫자(n) 과 최대한 일치하게 같은 자리의 수(result) 만들기 (문자열로 입력받은 n을 훑으며 정수화하기)
- 해당 숫자의 버튼이 고장났다면 정상 버튼 중 최대한 가까운 버튼으로
- (이 과정에서 RuntimeError (NameError)가 발생한 것 같음)
-
result에서 +/- 통해 목표값으로 만들기
-
- 문제점 1
- 문제 조건 상, min_btn은 무조건 초기화된다고 생각했는데, 실제로는 그렇지 않음(btns 이 없는 경우도 있기 때문)
- 문제점 2
- 모든 경우를 만족시키지 않음 (abs(num-btn)으로 판단하면 안 됨)
- 반례)
- n = 1505
- 정상작동 버튼: 0, 1, 4, 6, 9
- 작성한 코드는 result를 1404/1406/1604/1606/…이라 생각할 것
- 하지만 1404/1606이 되면 안됨
import sys
input = sys.stdin.readline
n = input().rstrip()
m = int(input())
btns = set(i for i in range(0, 10)) - set(map(int, input().split()))
result = 0
cnt = 0
# 같은 자릿수 만들기
for num in n:
num = int(num)
# 버튼이 정상작동 하는 경우
if num in btns:
result *= 10
result += num
cnt += 1
# 버튼이 고장난 경우
else:
min_value = 100
for btn in btns:
if min_value >= abs(num - btn):
min_value = abs(num-btn)
min_btn = btn
result *= 10
result += min_btn
cnt += 1
# 동일한 채널이 나올 때 까지 + / - 버튼 누르기
if result != int(n):
cnt += abs(result - int(n))
print(min(cnt, abs(100-int(n))))
방법 2 (옳은 풀이)
- 그냥 모든 경우를 다 따져봄!
- 0 <= N <= 500,000
- 채널은 0부터 무한대까지 => - channel은 1,000,000 까지 훑기 - ex) - n = 500,000 / 가능한 버튼: 8 1. 100 -> 500,000 : [499,900 번] 2. 888,888 -> 500,000 : [388,888 번] - 밑에서 목표값까지 ++보다 위에서 목표값으로 – 가 더 빠를수도 있음 (1,000,000은 적당히 큰 값을 그냥 넣은 것)
import sys
input = sys.stdin.readline
n = int(input())
_ = int(input())
# 정상 작동하는 버튼의 집합
btns = tuple(map(int, input().split()))
# 최솟값 초기값: 100에서 목표 채널까지 이동한 수
min_count = abs(100 - n)
# 모든 경우의 수 탐색
for channel in range(1000001):
channel = str(channel)
flag = 0
for ch in channel:
# 고장난 버튼이 있다면 break
if int(ch) in btns:
flag = 1
break
# 정상 작동한 버튼으로 만들어진 채널인 경우
# 최솟값 비교
if flag == 0:
min_count = min(min_count, abs(int(channel) - n) + len(channel))
print(min_count)