구현, 브루트포스 - 22251번: 빌런 호석

import itertools

line = list(map(int, input().split()))
n, k, p, x = line[0], line[1], line[2], line[3]

# 바꿀 수 있는 수 범위 : 1 ~ n
# 디스플레이 자리수: k
# 모든 숫자 내에서 반전시킬 수 있는 led 개수 : 최소 1 ~ 최대 p개
# 현재 엘베의 층 : x

# led 는 7개
#   0 1 2 3 4 5 6 
# 0:1 1 1 0 1 1 1
# 1:0 0 1 0 0 1 0
# 2:1 0 1 1 1 0 1
# 3:1 0 1 1 0 1 1
# 4:0 1 1 1 0 1 0
# 5:1 1 0 1 0 1 1
# 6:1 1 0 1 1 1 1
# 7:1 0 1 0 0 1 0
# 8:1 1 1 1 1 1 1
# 9:1 1 1 1 0 1 1

led_nums = [[1, 1, 1, 0, 1, 1, 1], [0, 0, 1, 0, 0, 1, 0], [1, 0, 1, 1, 1, 0, 1], [1, 0, 1, 1, 0, 1, 1], [0, 1, 1, 1, 0, 1, 0], 
            [1, 1, 0, 1, 0, 1, 1], [1, 1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 0], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 1, 1]]
x_nums = []

cost = [[0] * 10 for _ in range(10)]

# 모든 0~9 에서 0~9 로 led 변환하는 데 드는 비용 구해놓기
# cost[전 숫자][후 숫자]
for from_num in range(10):
    for to_num in range(10):
        cnt = 0
        for i in range(7):
            if led_nums[to_num][i] != led_nums[from_num][i]:
                cnt += 1
        cost[from_num][to_num] = cnt



# x 앞에 0 패딩 추가(k자리수에 맞추기)
if len(str(x)) < k:
    for i in range(k - len(str(x))):
        x_nums.append(0)

for i in range(len(str(x))):
    x_str = str(x)
    num = int(x_str[i])
    x_nums.append(num)


nums_can_be = []
for i in range(k):
    nums_can_be.append([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
# *은 argument unpacking, product()의 각 인자로 리스트들을 넘겨주는 역할
res = list(itertools.product(*nums_can_be))


#print(res)
total_count = 0

for r in res:
    r = list(r)
    this_cost = 0
    # 전체 자릿수의 led 전환 비용 구하기
    for i in range(k):
        t = r[i]
        s = x_nums[i]

        this_cost += cost[s][t]

    target = int(''.join(map(str, r)))

    # 범위 만족하고, 자기 자신이 아니면서, p 이하의 비용이라면 카운팅
    if 1 <= target <= n and target != x and this_cost <= p:
        #print(target)
        total_count += 1

print(total_count)