[백준] 1107 - 리모컨 (브루트포스)

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

1107번: 리모컨

n = int(input())
m = int(input())
lost = list()
 
if m > 0:
    lost = list(map(int, input().split()))
 
if n == 100:
    print(0)
elif n > 100:
    minv = 100
    maxv = 100
    for i in range(n, 100, -1):
        s = str(i)
        flag = True
        for c in s:
            if int(c) in lost:
                flag = False
        if flag:
            minv = i
            break
    for i in range(n, 2 * n - minv):
        s = str(i)
        flag = True
        for c in s:
            if int(c) in lost:
                flag = False
        if flag:
            maxv = i
            break
    if maxv == 100:
        val = (minv, abs(n - minv))
    else:
        val = (maxv, abs(n - maxv))
    print(min(abs(100 - n), len(str(val[0])) + val[1]))
else:
    minv = 100
    maxv = 100
    for i in range(n, 100):
        s = str(i)
        flag = True
        for c in s:
            if int(c) in lost:
                flag = False
        if flag:
            maxv = i
            break
    for i in range(n, -1, -1):
        s = str(i)
        flag = True
        for c in s:
            if int(c) in lost:
                flag = False
        if flag:
            minv = i
            break
    if abs(n - minv) > abs(n - maxv):
        val = (maxv, abs(n - maxv))
    else:
        val = (minv, abs(n - minv))
    print(min(abs(100 - n), len(str(val[0])) + val[1]))

브루트포스로 탐색하면 된다.

n에서 시작해서 고장나지 않은 버튼으로 만들 수 있는 수를 찾으면 '숫자 버튼으로만' 만들 수 있는 가장 가까운 값이 2개 나온다.

그 중에서 더 가까운 값을 찾고, 그 값과 오직 +나 -만 이용했을 때 더 적게 누르는 값을 찾으면 된다.

다만, n이 100보다 클 경우, n에서 작은 수 중에서 숫자 버튼으로 만들 수 있는 경우를 찾고, 이를 초과하지 않는 선에서 큰 수를 찾는 것이 좋다. 안그러면 시간초과 가능성이 있다.