[백준 / 파이썬] 백준 1107번 문제 풀이: 브루트 포스 (Brute Force)

리모컨

백준 1107번

Pixabay 로부터 입수된  André Santana Design André Santana 님의 이미지 입니다.

---

문제

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

 

입력

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

 

출력

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

 

 

문제 풀이

---

문제 접근

이 문제는 브루트 포스(Brute Force) 기법으로 접근할 수 있다.

 

수빈이는 목표 채널에 도달하기 위해 두 가지 방법을 사용할 수 있다

1. 고장나지 않은 채널 번호를 직접 입력하는 방법
2. + 버튼과 - 버튼을 이용하여 목표 채널로 이동하는 방법

그렇다면 버튼 입력 횟수는 (채널번호의 길이)+ (+,- 버튼을 누른 횟수)가 된다.

 

답을 구하기 위해서는

0부터 1,000,000까지 고장난 버튼을 포함하지 않는 모든 채널번호에 대해 버튼 입력 횟수를 구하고 그것의 최솟값을 구하면 된다.  

 

 

 

왜 1,000,000까지의 채널을 검사해야 할까?

만약 500,000까지의 채널만 검사하고 고장난 버튼이 1, 2, 3, 4, 5라고 가정하면, 목표 채널 100에 도달하기 위해서는 100에서 + 버튼을 눌러 500,000까지 이동해야 한다. 이는 499,900번을 +버튼을 눌러야 하는 비효율적인 방법이 된다.

그러나 1,000,000까지 검사하면 600,000에서 - 버튼을 이용해  500,000으로 이동하는 방법을 고려할 수 있다. 이 경우 -버튼을 100,000번 누르면 돼서 효율적이다.

따라서, 1,000,000까지의 채널을 검사함으로써, 고장난 버튼이 있더라도 목표 채널에 더 가까운 채널 번호를 찾을 수 있고, 이를 통해 최소 이동 횟수를 찾는 것이 가능하다.

 

문제 해결

입력 받기

import sys
N = int(sys.stdin.readline())  # 목표 채널 번호
M = int(sys.stdin.readline())  # 고장난 버튼의 개수 (이 변수는 사용되지 않음)
broken_button = sys.stdin.readline().split()  # 고장난 버튼 번호 리스트

• N은 목표 채널 번호이다.
• M은 고장난 버튼의 개수이다. 코드에서는 이 값을 직접 사용하지 않지만, 입력으로 받아야 한다.
• broken_button은 고장난 버튼을 문자열 리스트로 저장한다

 

초기값 설정

minimum = abs(N - 100)  # 초기값을 100에서 목표 채널까지의 +, -버튼 입력 수

초기값은 단순히 100에서 목표 채널 N까지 이동하는 데 필요한 버튼 클릭 수 이다. 이는 고장난 버튼을 고려하지 않고 +, - 버튼만 사용할 때의 클릭 수이다.

 

모든 가능한 채널 번호 검사

for test_num in range(1000001):
    test_num = str(test_num)  # 채널 번호를 문자열로 변환

• 0부터 1,000,000까지의 모든 채널 번호를 검사한다.
• 채널 번호를 문자열로 변환하여 각 자리수를 쉽게 검사할 수 있도록 한다

 

고장난 버튼 확인

flag = 0
    for j in test_num:
        if j in broken_button:
            flag = 1
            break

• 현재 채널 번호의 각 자리를 검사하여 고장난 버튼이 포함되어 있는지 확인한다.
• 고장난 버튼이 포함되어 있다면 flag를 1로 설정하고 반복문을 종료한다.

 

유효한 채널 번호 처리

 if flag == 0:
        minimum = min(minimum, abs(int(test_num) - N) + len(test_num))

• 현재 채널 번호가 고장난 버튼을 포함하지 않으면 유효한 채널 번호로 간주한다. 이는 flag의 값을 통해 확인할 수 있다
• 목표 채널 N까지 도달하는 데 필요한 버튼 클릭 수를 계산한다 .
  • abs(int(test_num) - N)는 현재 채널 번호에서 목표 채널까지의 차이이다.
  • len(test_num)는 현재 채널 번호를 입력하는 데 필요한 버튼 수이다.
• 이 값을 현재까지의 minimum 값과 비교하여 더 작은 값을 minimum에 저장 한다 .

 

결과 출력

print(minimum)

최종적으로 계산된 최소 버튼 클릭 수를 출력한다.

 

제출 코드

import sys
N=int(sys.stdin.readline())
M=int(sys.stdin.readline())
broken_button=sys.stdin.readline().split()
minimum=abs(N-100)
for test_num in range(1000001):
    test_num=str(test_num)
    flag=0
    for j in test_num:
        if j in broken_button:
            flag=1
            break
    if flag==0:
        minimum=min(minimum,abs(int(test_num)-N)+len(test_num))

print(minimum)