문제
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다.
어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
아이디어 1
- 버튼이 고장 안 난 케이스: 두번째 입력이 0인 경우
- 숫자 버튼 그대로 누르면 됨.
- 숫자 길이가 곧 답.
여기까지 코드
python
import sys
input = sys.stdin.readline
ch = input()
malfunc = int(input())
if malfunc == 0:
print(len(ch))
- 버튼이 고장난 케이스: 두번째 입력이 0이 아닌 경우
- 채널이 100인 경우 : 그냥 0 출력
고장 난 버튼에 채널 번호 자릿수들이 몇 개나 포함되어 있는가?
- 다 안 맞다.
- 100보다 크다면, 채널 - 100만큼 ‘+’ 누르기
- 100보다 작다면, 100 - 채널 vs 채널+1 비교
-
100 - 채널이 크면 “채널+1” 만큼 버튼 누르기
(0번 누르고, “채널” 번 만큼 ‘+’ 누르기)
-
작으면 “100 - 채널”만큼 ‘-’버튼 누르기
-
여기까지 코드
python
else:
button_list = list(map(int, input().split()))
case = 0
if int(ch) == 100:
print(0)
exit()
for number in set(ch):
if int(number) in button_list:
case += 1
if case == len(ch):
if int(ch) > 100:
print(int(ch) - 100)
else:
if 100 - int(ch) > int(ch) + 1:
print(int(ch) + 1)
else:
print(100-int(ch))
- 1 < (안 맞는 거) < 전부
- 하나씩 빼가면서 (
for i in range()) 확인 - i에 고장난 버튼이 없다면,
채널 - i계산 - a = (채널 - i)의 자릿수 + (채널 - i)
- 하나씩 더해가며 (
for i in range()) 확인 - i에 고장난 버튼이 없다면,
i - 채널계산 - b = (채널 - i)의 자릿수 + (i - 채널)
- a vs b 해서 더 작은 거 출력
- 하나씩 빼가면서 (
여기까지 코드
python
elif case < len_ch:
channel = int(ch)
a, b = 0, 0
while 1:
channel -= 1
included = 0
for x in str(channel):
if x in button_list:
included += 1
if included == 0:
n1 = int(ch) - channel
a = len(str(n1)) + n1
break
while 1:
channel += 1
included = 0
for x in str(channel):
if x in button_list:
included += 1
if included == 0:
n2 = int(ch) - i
b = len(str(n2)) + n2
break
print(min(a, b))
이렇게 했더니…시간이 너무 오래걸린다.
아이디어 2
100번 → 희망채널 n번으로 가는 방법
- 100번 → n번
- ‘+-’으로 이동
- 100번 → 중간번호 → n번
- 100번에서 중간번호: 직접 번호입력
- 중간번호에서 n번: ‘+-’으로 이동
직접 번호를 입력할 리모콘: 고장난 번호 수와 종류가 지정됨.
고장난 버튼 리스트 = 원소가 문자열인 배열로 받는 것이 좋음
중간번호 찾아내기 (2번 방안)
반복문을 계속 돌리기. for i in range …
만약 고장난 버튼 리스트에 i가 있다면 pass
- i를 문자열로 바꿔서 자릿수 별로 봐야 한다.
없다면,
- i를 문자열로 바꾼 것의 길이 + (희망 채널 - i) 와 1번 방안 비교
python
import sys
input = sys.stdin.readline
aim_ch = int(input())
malfunc = int(input())
if malfunc != 0:
malfunc_list = list(input().split())
else:
malfunc_list = []
# 1번 방안
ans = abs(aim_ch - 100)
# 2번 방안
for i in range(1000001):
count = 0
for num in str(i):
if num in malfunc_list:
count += 1
# 1번 vs 2번 방안 계속 비교
if count == 0:
ans = min(ans, abs(aim_ch - i) + len(str(i)))
print(ans)