[백준BOJ] 1107번 리모컨.py

 

백준 저지에서 리모컨을 파이썬을 통해 풀어 보았다. 

 

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

1107번: 리모컨

1107번 리모컨.py

tomy9729/Algorithm

 

 

1107번 리모컨

문제

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

설명

브루트 포스 문제인데 주의할게 많은 문제이다. 반례나 코드 작성하는 데 있어 여러 가지를 배울 수 있었다. 

 

원하는 채널까지 가는데 버튼을 누르는 최소 횟수를 구해야 한다. 이로 인해 전제조건이 붙는다. +나 -를 섞어서 사용하면 안 된다. 채널 이동을 하지 않고 +나 -만을 사용해서 이동하는 게 최소 횟수일 수 있다.

 

처음에는 N과 가장 가까우면서 고장 나지 않은 번호로 이뤄진 채널로 이동하는 알고리즘을 구현하려고 했다. 여러 가지 시도를 했지만 결국 실패했다.

 

다음으로 채널 N에서 위아래로 한 칸씩 이동하며 가장 먼저 고장 나지 않은 번호로만 이뤄진 채널이 나올 때까지 확인했다. 이를 확인하기 위해 고장 난 번호와 현재 채널의 번호를 set으로 표현하여 교집합을 통해 확인했다. 이 경우 양의 방향으로 이동하는 도중 자릿수를 넘어가는 경우를 확인하지 못해서 실패했다. 예를 들어 숫자 1만 고장 나지 않았고 채널 6으로 이동할 경우 채널 1로 갈 때가 최소 횟수이지만 11로 이동하기도 했는데 예외 처리를 하지 못했다.

 

최종적으로 모든 채널에 대해 확인하여 풀었다. 이동 가능한 채널은 500000개인데 두 배인 1000000까지 확인하더라도 시간 초과에 걸리지 않는다. result를 +나 -로만 이동했을 경우의 횟수로 설정하고 이동하는 채널을 0번부터 1000000번까지 모두 확인하여 가장 최소 횟수를 구했다.

 

만약 M이 0일 경우 고장 난 번호에 대해 아무런 숫자도 입력되지 않기 때문에 예외 처리를 하지 않으면 에러가 발생한다.

코드

#1107번 리모컨
if __name__ == "__main__":
  n = input()
  m = int(input())
  if m != 0 : 
    broken = set(map(int,input().split()))
  else : 
    broken = set()

  now = 100
  if int(n) == 100 : 
    print(0)
  elif m == 10 : 
    print(abs(int(n)-100))
  else :
    n = int(n)
    result = abs(int(n)-100)
    for i in range(1000001) : 
      num = set(map(int,list(str(i))))
      if num & broken == set() :
        if result > len(str(i)) + abs(n-i) : 
          result = len(str(i)) + abs(n-i)
    
    print(result)