[백준] 1107 리모콘 (python 파이썬)

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

1107번: 리모컨

---

 

아이디어

1. 알고리즘 선택

• 처음 문제를 보고 DP로 풀어야 하나 생각하면서 도저히 모르겠어서 알고리즘 분류를 보니까 그냥 브루트 포스 문제다.

2. 구현

• 먼저 현재 채널(100)에서 최소값이 나올 수 있는지 확인
• 이후 0부터 1000000까지 버튼으로 만들 수 있는 채널인지 확인
• 그 채널 숫자를 만드는데 필요한 버튼 개수 확인

---

코드 설명

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

if M != 0:
    broken_button = [int(x) for x in input().split()]
else:
    broken_button = []

result = abs(100 - N)

입력할때 고장 난 버튼이 없으면 입력이 없으니까 처리해둠.

처음 채널 100에서 +, - 채널 이동한 것이 답일 수도 있으므로 result값 abs(100 - N)으로 설정

 

for num in range(1000001):
    n = [int(x) for x in list(str(num))]

    for i in range(len(n)):
        if n[i] in broken_button:
            break

        if i == len(n) - 1:
            count = len(n) + abs(N - num)
            result = min(result, count)
print(result)

0부터 1000001까지 for문 실행.

N 최대값은 500000이지만 숫자가 위에서 내려오는 경우도 있으므로 1000000까지 반복

예를 들어 N = 500000이고 고장 난 버튼이 1 2 3 4 5 6 7 9 0 일 때 888888에서 내려오는 게 더 빠르다.

 

해당되는 숫자가 만드는게 가능하면 result값을 업데이트해주고 아니면 다음 수로 넘긴다.

버튼 누른 횟수는 숫자길이 + 해당 숫자와 N의 차이 

 

---

 

전체 코드

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

if M != 0:
    broken_button = [int(x) for x in input().split()]
else:
    broken_button = []

result = abs(100 - N)

for num in range(1000001):
    n = [int(x) for x in list(str(num))]

    for i in range(len(n)):
        if n[i] in broken_button:
            break

        if i == len(n) - 1:
            count = len(n) + abs(N - num)
            result = min(result, count)
print(result)

브루트포스와도 친해져야겠다고 생각한 문제