백준 1107 리모컨 Python

문제설명

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

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

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

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

제한사항

 

입력

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

출력

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

예제

---

이 문제의 key포인트

-> 반례가 많다..

처음에 알고리즘을 짤 때 최대한 빈틈없이 짜려고 노력하는 것이 좋을 듯하다.

---

자료구조 및 알고리즘: 브루트포스

---

문제풀이

첫번째 풀이(완성코드)

# BOJ 1107
# 64ms
# 30840KB
# brute force

import sys
input = sys.stdin.readline

button = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
broken = []
N = int(input()) # 가고싶은 채널
M = int(input()) # 고장난 버튼의 개수
if M != 0:
    broken = map(int, input().split())
button = list(set(button) - set(broken)) # 남은 버튼

# 근사 함수
def approx(num):
    temp = str(num)
    for i in temp:
        if int(i) not in button:
            return False
    return True

# 1. 가고싶은 채널에서 현재채널 차이만큼 +나 -누르기
if N >= 100:
    min1 = N - 100
else:
    min1 = 100 - N

# 2. 가고싶은 채널 근사치 만들기
if button != []:
    impossible = 0

    # 아래로 근사치
    num_minus = N
    while 1:
        # 아래로 근사치 만들 수 없는 경우
        if num_minus < 0:
            impossible = 1
            break
        
        if approx(num_minus) == True:
            break
        num_minus -= 1

    # 위로 근사치
    num_plus = N
    while 1:
        if approx(num_plus) == True:
            break

        # 아래로 근사치했을 때 최소값을 넘어버리면 위로 근사치 찾기 중지
        if impossible != 1 and num_plus - N > N - num_minus:
            break
        num_plus += 1

    min2 = len(str(num_plus)) + num_plus - N
    if impossible == 1:
        min3 = sys.maxsize
    else:
        min3 = len(str(num_minus)) + N - num_minus
    
else:
    min2 = sys.maxsize
    min3 = sys.maxsize

print(min(min1, min2, min3))

한번에 맞은 것은 아니고 반례들을 찾아가면서 코드를 수정시켰다. 

처음에 고려한 알고리즘은 다음과 같다.

 

1. +나 - 버튼만을 이용하는 경우

    -> abs(가고싶은 채널 - 현재 채널(100))

2. 누를 수 있는 번호버튼을 이용하는 경우

    N값을 기준으로 1씩 +하거나 -함으로써 해당 값을 누를 수 있는 모든 버튼이 존재하면 이 값에서

    가고싶은 채널까지 +나 - 버튼을 누르게 함

    -> 가고싶은 채널 기준 위로 근사치 (N + 1 ...)

    -> 가고싶은 채널 기준 아래로 근사치 (N - 1 ...)

 

이렇게 구현 시 처리해줘야할 점 

(1) 가고싶은 채널 기준 아래로 근사치를 만들 수 없는 경우

    예를 들어 가고싶은 채널이 8번 채널이지만 고장난 버튼이 0, 1, 2, 3, 4, 5, 6, 7, 8 인 경우

    아래로 근사치를 만들 수 없음. 따라서 이 경우에 impossible 변수를 이용해서 impossible의 경우에 아래로 근사치했      을 경우 최소 버튼클릭수를 sys.maxsize값으로 지정해줬다.

 

(2) 누를 수 있는 버튼이 없는 경우

     고장난 버튼이 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 모든 버튼이 고장났을 경우엔 +나 -로 채널 옮기는 경우만 고려하도록 함

     (button != [] 일때만 2번 경우 고려)

 

(3) 위로 근사치 찾을 때, 아래로 근사했을 때의 최소값을 넘어버리면 중지

     이걸 제한을 걸어주지 않으면 while문에서 무한루프를 돌게됨

     반례: 예제 6번