백준 / 1107번 리모컨 / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 1107번 리모컨

문제 사이트: https://www.acmicpc.net/problem/1107

1107번: 리모컨

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

90750

22090

15479

22.837%

문제

수빈이는 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 복사

6

예제 입력 2 복사

100
5
0 1 2 3 4

예제 출력 2 복사

0

예제 입력 3 복사

500000
8
0 2 3 4 6 7 8 9

예제 출력 3 복사

11117

예제 입력 4 복사

100
3
1 0 5

예제 출력 4 복사

0

예제 입력 5 복사

14124
0

예제 출력 5 복사

5

예제 입력 6 복사

1
9
1 2 3 4 5 6 7 8 9

예제 출력 6 복사

2

예제 입력 7 복사

80000
2
8 9

예제 출력 7 복사

2228

힌트

예제 1의 경우 5455++ 또는 5459--

출처

• 데이터를 추가한 사람: applyoo
• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: jh05013

알고리즘 분류

보기

---

나의 풀이

 

전형적인 탐색 문제이다.

처음에 제대로 못풀었는데 , 접근을 프로그래머스에 나오는 마법의 엘레베이터 처럼 접근했었다..

근데 해당 문제에서 리모컨이 고장난 상황도 필요하므로 해당 부분을 고려해야하는게 핵심이다.

그리고 현재 수빈이가 보고있는 채널이 100번이라는 조건이 있으므로 해당 조건도 고려하여야한다.

 

또한 수빈이가 볼 수 있는 채널은 무한대라는 가정이 있으므로, 입력값 제한은 500000으로 되어있지만,

 

import sys
input = sys.stdin.readline

target = int(input())
n = int(input())
error = list(map(int, input().split()))


def solve(target,n,error):
    now_channel = 100 # 수빈이가 현재 보고 있는 채널
    min_cnt = abs(100 - target)
    for i in range(1000001):
        nums = str(i)
        for j in range(len(nums)):
            if int(nums[j]) in error:
                break
            elif j == len(nums) -1:
                min_cnt = min(min_cnt, abs(int(nums) - target) + len(nums))
    
    return min_cnt
print(solve(target,n,error))

 

만약에 수빈이가 이동하려는 채널이 500,000이고, 리모컨의 숫자 중 1, 2, 3, 4, 5가 고장났다고 가정하자.

 

이 때, range의 범위가 500,000으로 제한되면, 시작점인 100번에서 +만 눌러서 500,000까지 도달하는 총 499,900번 버튼을 클릭하게 할 것이다.

 

하지만 물론 이것은 최적의 해가 아니다.

 

600,000에서 -를 100,000번 눌러 target에 도달하는 것이 최적의 해일 것이다.

 

이러한 이유 때문에 range는 1,000,000까지로 설정해주어야 한다. (출처)[https://seongonion.tistory.com/99]

8

---

※ 알아야 할 것

- 모든 문제를 엄청 어렵게까진 접근 안해도 된다 단순하게 생각하는 힘을 기르자...