[백준] 1107번 - 리모컨 | 파이썬

SangJin Ham·2023년 9월 9일

백준 브루트포스 알고리즘

백준

목록 보기

50/51

1107번 - 리모컨

시간제한 : 2초
메모리 제한 : 256MB

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

5457
3
6 7 8

예제 출력 1

코드

import sys

# 목표 채널 번호
N = int(sys.stdin.readline().strip())

# 고장난 버튼의 개수
M = int(sys.stdin.readline().strip())

broken = []
# 고장난 버튼이 있는 경우에만 추가
if M != 0:
  broken = list(map(int, sys.stdin.readline().strip().split()))

# 채널 100에서 +나 -만 사용해 이동하는 경우
ans = abs(100 - N)

for x in range(1000001):
  num = str(x)

  for i in range(len(num)):
    # 현재 x의 자리수 하나하나가 버튼에 존재하는지 확인
    if int(num[i]) in broken:
      break
    # 마지막 자리수까지 위 if문(버튼 존재)을 통과했냐 ?
    elif i == len(num) - 1:
      # 최소 횟수 = min(현재 최소 횟수, abs(목표 채널 - x 채널) + x 채널의 길이(버튼 누르는 횟수)
      ans = min(ans, abs(x-N) + len(num))

print(ans)

풀이

시간 : 2900ms
메모리 : 31256KB

이 문제는 브루트포스 알고리즘을 이용하는 즉, 모든 경우의 수를 다 탐색하는 문제다.

나는 탐색을 할 때 수빈이가 이동하려고 하는 채널이 (0 ≤ N ≤ 500,000)라고 해서 범위를 500,000까지 잡았었다.

하지만 생각해보니 만약 수빈이가 500,000번 채널에 이동하려고 할 때,
1 ~ 5번까지의 버튼이 고장났다고 한다면
수빈이의 초기 채널 100번에서 +버튼으로 움직이는 방법말고는 없다는 걸 알았다.
물론 600,000번 채널에 가서 -버튼으로 움직이는 게 리모콘 조작횟수가 적다.
따라서 500,000의 두 배인 1,000,000로 범위를 잡았다.

또, 0부터 1,000,000까지 탐색하면서
만약 x가 1234라고 했을 때, x의 자릿수마다 고장난 버튼이 있는지 확인하고
고장난 버튼이 있다면 해당 번호는 넘어갔다.

만약 x의 모든 자릿수가 고장나지 않은 버튼이라면,
x - 이동하려고 하는 채널의 절대값과 x로 이동하려면 리모콘으로 눌러야하는 x의 자릿수 개수와 더해 현재까지의 최소 조작횟수와 비교해 둘 중 작은 값을 ans에 저장했다.

그렇게 탐색이 종료된 후 목표 채널 N에 도달하기 위한 최소 횟수가 저장된 ans를 출력해준다.