[백준] 1107 리모컨 python

www.acmicpc.net/problem/1107

1107번: 리모컨

import sys
input = sys.stdin.readline

want_ch = input().rstrip()
want_ch_list = list(map(int, list(want_ch)))
want_ch = int(want_ch)
use_set = set(range(10))
M = int(input())
if M:
    crashed_set = set(map(int, input().split()))
    use_set = use_set - crashed_set


result = 500000
min_distance = 500000
min_dist_val = -1
def backtrack(ind=0, cur_ch=100, index=0):
    global result, min_distance, min_dist_val
    if cur_ch == want_ch:
        result = min(result, ind)
        min_distance = 0
        return

    dist = abs(cur_ch - want_ch)
    if min_distance > dist:
        min_distance = dist
        min_dist_val = cur_ch
        result = ind if ind else result
    elif min_distance == dist:
        if min_dist_val > cur_ch:
            min_dist_val = cur_ch
            result = ind
        elif min_dist_val == cur_ch:
            if result > ind:
                result = ind

    if index == len(want_ch_list) + 1:
        return
        ### index에서 하나더 가는경우까지 조사

    for num in list(use_set):
        if index == 0:
            cur_ch = 0
        backtrack(ind + 1, cur_ch * 10 + num, index + 1)

backtrack()
print(min(result + min_distance, abs(100 - want_ch)))

백트래킹으로 모든 조합을 만들어가면서 조합을 확인했다.

너무 더러워서 보여주기 조금 부끄러운 코드이다.

10
1
0
ans: 2
---
0
3
0 1 2
ans: 4
---
0
10
0 1 2 3 4 5 6 7 8 9
ans: 100
---
0
9
0 1 2 3 4 5 6 7 8
ans: 10
---
1
9
1 2 3 4 5 6 7 8 9
ans: 2
---
1020
0
ans: 4
---
0
0
ans: 1

---

---

import sys
input = sys.stdin.readline

def check(num):
    num = list(str(num))
    for i in num:
        if i in s: 
            return False
    return True

n = int(input())
m = int(input())
s = list(input().strip()) if m else list()
result = abs(n - 100)
for i in range(1000001):
    if check(i):
        result = min(result, len(str(i)) + abs(i - n))
print(result)

타인의 코드

너무 간단해서 어이가 없었다. 이런방법이 있었구나...