[백분] 1107: 리모컨 파이썬 풀이 - 부르트포스

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

1107번: 리모컨

 

 

1107 질문 게시판

다행히 리모컨은 부시지 않았습니다.

 

 

처음에는 그리디로 접근을 하다가 반례 해결이 도저히 안돼서, 부르트포스 방식을 생각하게 됐습니다.

풀이는 다음과 같습니다.

1. 채널 버튼을 누르지 않고 이동하는 경우를 구한다.

2. 누를 수있는 채널 버튼들로 중복조합을 구한다.

3. 중복 조합을 통해서 이동하는 경우가 버튼을 최소로 누르는 방법이면 업데이트한다.

 

 

풀이는 좋았으나, 실수를 연속해서 고치다보니 여기저기서 또 다른 실수가 생겨가지고 (96에서 WA) 결국엔 혼자서 해결을 못하고 질문게시판에서 반례를 답변받았습니다. (처음 코드에선 M=0인 경우에 조기종료를 했는데, 이때 채널 버튼을 누르지 않고 이동하는 경우를 고려하지 못했습니다.)

-> 잘못된 코드 유지보수 할 바에, 새로 만드는게 낫다는 말이 떠올랐습니다. 물새는 파이프에 계속 테이프 덧칠하는 것 보다는 그냥 처음부터  다시 만들자구요. 맞왜틀이 3번이상 반복된다면 코드를 깔끔하게 새로 작성해야겠습니다.

 

그리고 이문제에선 EOF에러가 났었는데, 이 에러는 백준에서 입력이 다 끝났는데, 프로그램에선 입력을 계속 대기하는 상태의 에러입니다. 프로그램 입장에선 입력 부족이겠죠.

해당 문제에선  M=0인 경우엔 더이상 입력이 안들어오는데 이에 대한 처리를 안한 경우 EOF에러가 발생했습니다.

 

def sol(depth, length):
    global ans

    if depth == length:
        cur = int(''.join(map(str, d)))
        ans = min(ans, abs(int(N)-cur) + length)
        return

    for i in range(10):
        if not wrong[i]:
            d.append(i)
            sol(depth+1, length)
            d.pop()


N = input()
M = int(input())
wrong = [False]*10
if M>0:
    for i in list(map(int, input().split())):
        wrong[i]=True

# 채널 버튼 안 누르는 경우
ans = abs(int(N)-100)

# 채널 버튼 누르는 경우
d = []
for i in range(1, len(N)+2):
    sol(0, i)

print(ans)