1107: 리모컨 (브루트포스)

1107번: 리모컨

뭔가 그리디 문제 같아서 처음에는 다음과 같이 접근했다.

n = 42798, 고장난 버튼 = [1,3,5,6,7,9] 라고 했을 때 42까지는 그대로 사용하고 그 뒤가 800 혹은 488인 경우가 있을텐데 여기서 단순히 +,- 해서 누른 버튼의 수의 최소를 구하고자 하였다. 좀 복잡하게 구현하긴 했지만 문제에 있는 test case는 잘 작동했으나 제출해봤을 땐 실패했다. 

n = input()
m = int(input())
broken_buttons = list(map(int,input().split()))
buttons = [i for i in range(0,10)]
buttons = [x for x in buttons if x not in broken_buttons]
d = []
case1,case2 = 0,0
sol = ""
for i in range(len(n)):
    if int(n[i]) in buttons:
        sol += n[i]
if int(n)==100:
    print(0)
elif len(sol)==len(n) and int(n)!=100:
    print(len(sol))
# len(sol)와 len(n)이 다를때
elif len(sol) != len(n):
    dif = [x-int(n[len(sol)]) for x in buttons]
    for i in range(len(dif)-1):
        if dif[i]<0 and dif[i+1]>0:
            case1 = sol+str(buttons[i])+str(buttons[0])*(len(n)-len(sol)-1)
            case2 = sol+str(buttons[i+1])+str(buttons[-1])*(len(n)-len(sol)-1)
            break
        else:
            case1 = sol+str(buttons[0])*(len(n)-len(sol))
            case2 = sol + str(buttons[-1]) * (len(n) - len(sol))
            break
    print(min(abs(int(case1)-int(n)),abs(int(case2)-int(n)))+len(n))

 

내가 시도한 저 아이디어는 len(sol)과 len(n)이 같을 때는 항상 맞는 것 같지만, 다를 때는 다양한 반례가 있다. 그렇지만 위의 시도가 의미가 있는게 "len(sol)!=len(n) 인 경우에는 +이나 -중 하나만을 이용하여 계산해야 함 " 이라는 점을 알아냈다.

 

이때 문제에서 n의 범위를 다시보니 0 ≤ N ≤ 500,000 이다. 가능한 N의 범위가 매우 작으니까 브루트포스로 풀어도 되겠다고 생각했다. 이때 N의 범위가 500,000 이하이지만, 망가진 리모컨으로 입력한 수는 500,000 보다 커도 상관없다. 다만 1,000,000을 넘어서면 0에서 +1 한 것보다 큰 수가 나오므로 0이상 999,999 이하의 범위에서 브루트포스를 시도해보았다. 또한 M=10 때, 숫자를 누르지 않을 때의 경우를 고려하여 아래와 같이 코드를 작성함

 

m = int(input())
broken_buttons = list(map(int,input().split()))
buttons = [i for i in range(0,10)]
buttons = [x for x in buttons if x not in broken_buttons]
sol = ""
for i in range(len(n)):
    if int(n[i]) in buttons:
        sol += n[i]
if int(n)==100:
    print(0)
elif len(sol)==len(n) and int(n)!=100:
    print(len(sol))
# len(sol)와 len(n)이 다를때
else:
    memo = abs(100 - int(n))  # + 혹은 -만 누를 때는 숫자 버튼 누른 거 세지않음
    for i in range(1000000):
        cnt = 0
        for j in str(i):
            if int(j) not in buttons: break
            cnt += 1
            if cnt == len(str(i)):
                if abs(i-int(n))+len(str(i)) < memo: memo = abs(i-int(n))+len(str(i))
    print(memo)
​

 

그런데 또 틀렸다고 한다. 내가 고려한 경우가 '아무것도 누르지 않을 때', '+,-를 누르지 않을 때', '+혹은 -를 누를 때'로 구분했는데 나는 여기서 '당연히 크기 순서는 아무것도 누르지 않을 때 < +,- 를 누르지 않을 때 < +혹은 - 를 누를 때' 라고 가정을 했기에 틀렸다고 생각했다. 하지만 101 을 생각해보면 + 한번 누르는 것이 버튼을 누르는 것보다 더 적은 반례가 존재한다. 즉 +,- 만으로 할 때, 숫자만으로 할 때의 경우를 고려해 비교하는 방식으로 코드를 다시 작성했다.

 

n = input()
m = int(input())
broken_buttons = list(map(int,input().split()))
buttons = [i for i in range(0,10)]
buttons = [x for x in buttons if x not in broken_buttons]
# +혹은 -를 누르지 않을 때
def solve1(n,array):
    cnt = 0
    case1 = 999999
    for i in n:
        if int(i) not in array: break
        cnt += 1
        if cnt == len(n):
            case1 = len(n)
    return case1

# + 혹은 -를 누를 때,
def solve2(n,array):
    case2 = abs(100 - int(n))  # + 혹은 -만 누를 때는 숫자 버튼 누른 거 세지않음
    for i in range(1000000):
        cnt = 0
        for j in str(i):
            if int(j) not in array: break
            cnt += 1
            if cnt == len(str(i)):
                if abs(i-int(n))+len(str(i)) < case2: case2 = abs(i-int(n))+len(str(i))
    return case2

print(min(solve1(n,buttons),solve2(n,buttons)))​

초반에는 잘 진행이 되었지만 뒤쪽에서 런타임에러가 발생하였다...

여기서 '버튼의 수에 따라 런타임 에러가 발생할 수 있을까?' 에 초점을 맞춰 계속 머리를 굴렸다. M = 0 일 때를 생각해보면 3번째 input으로 뭐가 들어올까 생각해보면 아무것도 입력하지 않을 것이다. 그렇다 여기서 런타임 에러가 발생한 것이다. M=0 일 때는 입력을 받지 않아야 한다. 이 조건을 추가시키고(런타임 에러 방지) 위에서 버튼을 list 형식으로 나타내지 않고 set으로 나타내었다(단지 코드상 편의). 

n = input()
m = int(input())
btns = set([i for i in range(10)])
btns -= set(map(int,input().split(' '))) if m!=0 else set()

따라서 최종적으로 작성한 코드는 아래와 같다. 

복잡해 보일 때는 때로는 간단히 문제조건을 봐서 무식하게 돌리는 것이 방법이 될 수 있는 것 같다.

n = input()
m = int(input())
btns = set([i for i in range(10)])
btns -= set(map(int,input().split(' '))) if m!=0 else set()


# +혹은 -를 누르지 않을 때
def solve1(n,btns):
    cnt = 0
    case1 = 999999
    for i in n:
        if int(i) not in btns: break
        cnt += 1
        if cnt == len(n):
            case1 = len(n)
    return case1

# + 혹은 -를 누를 때,
def solve2(n,btns):
    case2 = abs(100 - int(n))  # + 혹은 -만 누를 때는 숫자 버튼 누른 거 세지않음
    for i in range(1000000):
        cnt = 0
        for j in str(i):
            if int(j) not in btns: break
            cnt += 1
            if cnt == len(str(i)):
                if abs(i-int(n))+len(str(i)) < case2: case2 = abs(i-int(n))+len(str(i))
    return case2

print(min(solve1(n,btns),solve2(n,btns)))​