[백준/1107] 리모컨

리모컨

Baekjoon Online Judge

 

이 문제는 세 가지 함정이 있다ㅠㅠ  해당 블로그에서 잘 짚어주셨고, 이를 참고하여 문제해결에 반영하였다.

1. 시작값(100)에서 +, - 버튼 조작으로 타겟 채널로 이동 vs 숫자 버튼을 통해 타겟 채널로 이동 
2. 고장난 버튼이 없을 때, 입력을 받지 않음
3. 차이의 최솟값을 구하는 게 최선이 아닐 수 있음

 

---

알고리즘

1. 시작값(100)에서 타겟값까지의 차이

해당 문제의 예시에도 잘 나와있듯이, N = 100인 상황일 때는 당연히 리모컨을 조작하지 않아도 된다.

 

 

2. 고장난 버튼이 없을 때 입력을 받지 않음

m의 범위는 0 ~ 10이므로, m = 0 즉, 고장난 버튼이 없을 수도 있다. 이점을 간과했다.

 

 

3. 1번에서 걸러지지않았다면 당연히 최솟값을 구하는 것이 최선이라 생각했다.

예시 1번의 경우 '5457' 중 7이 고장난 버튼이니까 이와 차이가 최소이면서 고장나지 않은 5, 9를 선택한 뒤, ++ or -- 를 해줄 것이라고 생각했다.

 

그런데 아래 예시의 경우는 말이 달라진다.

1555
8
0 1 3 4 5 6 7 9

 

버튼 2, 8을 사용한 3가지 접근 방식은 다음과 같다.

 

(1) 기본값에서 + 로 접근한다.

• 1555 - 100 = 1455번

 

(2) 버튼을 1개씩 누르고, 남는 값은 + or - 로 처리한다.

• 1555는 2, 8 중 2와 최솟값을 가지니까 4번 모두 2222로 처리하고 (숫자 버튼 4번 클릭)
• 남은 (2222 - 1555 = 667) 것은 - 버튼으로 처리한다. ( - 버튼 667번 클릭)
• 총 4 + 667 = 671번

(3) 차이가 최소인 버튼은 아니지만 최솟값 도출이 가능한 케이스다.

• 888 3번 누른다. (숫자 3번 클릭)
• 남은 (1555 - 888 = 667) 것은 + 버튼으로 처리한다. ( + 버튼 667번 클릭)
• 총 3 + 667 = 670 번

그러니까 버튼의 차이를 최소로 고려해도 정답이 아닐 수도 있다는 것이다.

 

열심히 짯는데..

for item in channel:
    for button in remote:
        if item == button:
            ans.append(item)
            cnt += 1

    for j in brocken:
        if item == j :
            for button in remote:
                tmp = min(tmp, abs(button-j))

    for button in remote:
        if item - button == tmp:
            ans.append(button)
            cnt += 1

number = str()
num_channel = str()

for i in ans:
    number += str(i)

for i in channel:
    num_channel += str(i)

cnt += abs(int(num_channel)-int(number))

 

 

---

전체 코드

import sys;input=sys.stdin.readline

target = int(input())
m = int(input())
if m > 0: 
    brocken = input().rsplit()
else: 
    brocken = []

ans = abs(100 - target)

for i in range(1000001):
    is_possible = True
    for button in str(i):
        if button in brocken:
            is_possible = False
            break
    if is_possible:
        tmp = len(str(i)) + abs(i-target)
        ans = min(ans, tmp)

print(ans)

 

 

---

알게된 점

• 브루트포스가 짱!
• 내가 짠 코드가 길고 복잡할수록 정답과 멀어질 가능성이 있다, 단순하게 생각하자.