[파이썬(Python)] 백준 1107번: 리모컨

 

 

백준 1107번: 리모컨

문제 바로 가기

---

📌 문제

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

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

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

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

입력

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

출력

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

 

 

 

 

 

 

 

 

 

 

📝 아이디어

 

 

문제 분석 

 

주어진 문제는 리모컨을 이용하여 특정 채널 N으로 이동하는 최소 버튼 횟수를 구하는 문제입니다. 

• 현재 100번 채널에서 시작합니다.
• 리모컨에는 0부터 9까지의 숫자 버튼과 +, - 버튼이 있습니다.
• 일부 숫자 버튼이 고장날 수 있습니다.
• 목표 채널 $N \; (0 \leq n \leq 500,000)$으로 이동하는 최소 버튼 횟수를 구해야 합니다.

 

 

 

 

 

 

 

예제 분석

 

✅ 예제 1

5457
3
6 7 8

• 현재 채널: 100
• 고장난 버튼: 6, 7, 8
• +, - 버튼만 사용하는 경우: $|5457 - 100| = 5357$번 눌러야 하므로 비효율적
• 숫자 버튼 사용 가능 여부 확인
  • 5 4 5 7 → 모두 사용 가능
  • 숫자 버튼으로 직접 입력 가능 (4번 누름)

 

 

 

✅ 예제 2

100
5
0 1 2 3 4

• 현재 채널: 100
• 목표 채널: 100
• 이미 목표 채널에 있으므로 버튼을 누를 필요 없음

 

 

 

✅ 예제 3

500000
8
0 2 3 4 6 7 8 9

• 현재 채널: 100
• 고장난 버튼: 0, 2, 3, 4, 6, 7, 8, 9 → 사용 가능한 숫자는 1, 5
• +, - 버튼만 사용하는 경우: $|50000 - 100| = 499900$번 눌러야 하므로 비효율적
• 숫자 버튼으로 가장 가까운 숫자 찾기
  • 사용할 수 있는 숫자: 1, 5
  • 500000을 만들 수 없음 → 숫자 버튼으로 가장 가까운 값 찾기
  • 111111이 기장 가까운 숫자
• 조정 과정
  • 111111을 입력 → 6번 누름
  • 111111에서 500000까지 - 버튼을 38889번 누름
• 총 버튼 누름 횟수: $6 + 38889 = 11117$번 누름

 

 

 

 

 

 

 

아이디어

 

1️⃣ +, - 버튼만 이용하는 경우

 

 

현재 채널이 100이므로 + 또는 - 만 사용해서 이동할 경우

 

$$\text{pushed} = |N - 100|$$

 

즉, 현재 채널 100에서 목표 채널 N까지 단순히 증가 또는 감소만 사용할 경우의 버튼 횟수입니다. 

 

 

 

 

 

2️⃣ 숫자 버튼을 이용할 수 있는 경우

 

 

1. N을 숫자 버튼만으로 입력할 수 있는 경우

• 버튼 누름 횟수는 단순히 len(str(N))이 됩니다.

 

 

 

2. 숫자 버튼이 일부 고장난 경우

• N을 직접 입력할 수 있는지 확인합니다.
• 0 ~ 999999 범위에서 고장난 버튼 없이 만들 수 있는 숫자를 찾습니다.
• 해당 숫자를 입력한 후 +, - 버튼으로 조정합니다.  

 

 

 

 

 

3️⃣ 완전 탐색 (Brute Force)

 

 

0 ~ 999999 범위에서 N에 가장 가까운 유효한 숫자를 찾습니다.

 

1. 0 ~ 999999까지 숫자를 문자열로 변환하고, 고장난 숫자가 포함되는지 확인합니다.

2. 사용 가능한 숫자 중 N과 가장 가까운 숫자를 선택합니다.

3. 해당 숫자를 입력한 후 +, - 버튼으로 조정합니다.

3. 최소 버튼 누름 횟수를 찾습니다. 

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

n = int(input())
m = int(input())

if m != 0:  
    broken = list(map(int, input().split()))
else:
    broken = []

# 1. +, - 버튼만 이용
min_press = abs(n - 100)

# 2. 숫자 버튼 이용
for num in range(1000000):
    str_num = str(num)
    for digit in str_num:
        if int(digit) in broken:
            break
    else:
        presses = len(str_num) + abs(n - num)
        min_press = min(min_press, presses)
        
print(min_press)

 

Algorithm/백준/Gold/1107. 리모컨 at main · kuun1000/Algorithm