[Python] 1107. 리모컨(골5) - 브루트포스

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

1107번: 리모컨

---

2. 핵심 아이디어

파이썬은 1초당 약 100만회의 연산을 한다.

 

그렇게 가정을 했을 때 채널의 수인 50만회를

모두 순회하고 남을 시간이라는 판단을 할 수 있다.

 

즉, 0부터 채널의 수를 하나씩 바라보며

- 혹시 고장난 버튼의 숫자가 있는지 => 있으면 건너뜀

- 이곳까지 갈 수 있는 버튼 누르기 횟수가 더 작은지 비교

 

이런 연산을 해주면 된다.

 

여기서 주의할 점은 2가지이다.

 

1) 채널탐색의 범위

 

우리가 가고 싶은 채널은 0부터 50만까지 주어지나

실제로는 무한대로 존재한다.

 

따라서 탐색의 범위를 50만이 아닌 100만으로 설정해야 한다.

 

이는 +가 아닌 -로 탐색채널을 갈때를 고려한 숫자이다.

---

예시)

예를 들어 우리가 입력으로 주어지는 채널의 한계인

500,000채널에 가고 싶다고 가정하자

 

그리고 사용가능한 버튼은 5와 1밖에 없다.

 

500,000만까지 채널을 탐색하게 된다면

아마 155,555로부터 채널을 +하게 되는 루트가 가장 빠른 탐색이 된다.

 

그러나 (-)를 고려해 탐색범위를 100만으로 늘리면

우리는 511,111채널로부터 11,111회만에 50만 채널에 도달할 수 있다.

 

즉, 50만보다 더 위에서 채널을 내려오면서 찾을 케이스를 고려하기 위해

탐색의 범위는 50만이 아닌 100만이 된다.

---

 

두번째로 고려해야할 점은

우리가 지금보고 있는 채널이 100이라는 사실이다.

result=abs(int(channel)-100)

따라서, 초기에 비교할 값을 100번에서

채널까지 도달할 횟수로 초기화해주어야 한다.

 

 

 

---

3. 코드

channel = input()
p=int(input())
wrong_num=[]
if p!=0:
  wrong_num= list(map(int, input().split()))

result=abs(int(channel)-100)

for num in range(1000001):
  num= str(num)
  flag=True
  # 고장난 숫자가 있는지 확인
  if wrong_num:
    for i in wrong_num:
      if str(i) in num:
        flag=False
        break
  if flag==False:
    continue
  
  result= min(result, abs(int(num)-int(channel))+len(num))

print(result)

---

4.배운점

처음에는 중복순열을 통해 문제를 풀었으나, 결국 50만단위가 넘어가면서 숫자가 7자리 이상으로 커지자 메모리 초과가 났다. 브루트포스를 계속 그리디적으로 풀려고 노력하다보니 고민하는 시간이 길어졌던 것 같다.

 

가끔은 간단히 접근하는 것이 더 효율적일 때가 있음을 깨닫게 되었다.

특히 +/- 케이스를 모두 고려하여 탐색범위를 100만으로 정하는 것이 이번 문제의 핵심이 아니었나 생각한다.