[백준] 🏅1107번 리모콘(파이썬 Python)

1107번 문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.

 

입력

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

---

브루트포스 알고리즘

정의 : 무차별 대입 검색 또는 철저한 검색은 매우 일반적인 문제 해결 기술이자 각 후보가 문제 진술을 만족하는지 여부에 대해 가능한 모든 후보를 체계적으로 확인하는 알고리즘 패러다임입니다. (출처 : 위키백과)

 

지름길 없이 가능한 모든 경우의 수를 고려해야 한다.

따라서, 0부터 500000 채널을 모두 탐색하며 적절한 답을 찾아야 한다.

처음에 떠올린 솔루션은 수를 직접 완전탐색하지 않고 사용 가능한 숫자들의 조합으로 비교하려 했는데, 500001번까지 돌려도 시간 복잡도에 큰 차질은 생기지 않았다.

---

문제접근

1. 핵심은 'jump'하여 타겟 수인 N과 가장 차이가 적은 수로 이동하는 것과, 'jump'한 이후에 +, - 버튼을 몇 번 눌러야 하는지를 더해 비교하는 것이다.

2. 고장 나지 않은 버튼의 경우의 수를 고려하기 위해 최대 채널 수까지 모두 순회하며 고장난 버튼이 채널번호에 포함되는 경우 break한다.

• Python이 구현하기 매우 편리한 로직

3. 이후, count list에 해당 'jump'를 위해 눌러야 하는 횟수를 append하여 count list에서의 최소값을 구한다.

 

예외처리

• 입력 조건에 따르면 고장난 버튼이 없는 경우, 세번째 줄은 입력받지 않는다. 따라서 M의 개수에 따라 flag를 설정한다.
• 가고자 하는 채널이 100번이라면 0을 출력한다.
• 모든 버튼이 고장난 경우, jump 기능을 사용할 수 없다. 따라서 채널 N과 100번의 차이, 즉 직접 +와 -를 누르는 횟수를 출력한다.

---

코드

numbers = ['0','1','2','3','4','5','6','7','8','9']

N = int(input())
M = int(input())

flag = True if M==0 else False

def jump():
        count = [abs(100-N)]
        for i in range(1000000):
            for j in str(i):
                if j in broken:
                    break
            else:
                count.append(len(str(i))+abs(N-i))
        return min(count)
    
# 고장난 버튼이 없을 경우
if flag:
    print(min(len(str(N)), abs(N-100)))

if not flag:
    broken = list(map(str,input().split()))
    if len(broken)>0:   
        [numbers.remove(n) for n in broken]

    if N == 100:
        ans = 0
    elif M==10:
        ans = abs(N-100)
    else:
        ans = jump()

    print(ans)