BOJ 22251

🖋️ 문제

치르보기 빌딩은 $1$층부터 $N$층까지 이용이 가능한 엘리베이터가 있다. 엘리베이터의 층수를 보여주는 디스플레이에는 $K$ 자리의 수가 보인다. 수는 $0$으로 시작할 수도 있다. $0$부터 $9$까지의 각 숫자가 디스플레이에 보이는 방식은 아래와 같다. 각 숫자는 7개의 표시등 중의 일부에 불이 들어오면서 표현된다.

예를 들어 $K=4$인 경우에 $1680$층과 $501$층은 아래와 같이 보인다.

빌런 호석은 치르보기 빌딩의 엘리베이터 디스플레이의 LED 중에서 최소
$1$개, 최대 $P$개를 반전시킬 계획을 세우고 있다. 반전이란 켜진 부분은 끄고, 꺼진 부분은 켜는 것을 의미한다. 예를 들어 숫자 $1$을 $2$로 바꾸려면 총 5개의 LED를 반전시켜야 한다. 또한 반전 이후에 디스플레이에 올바른 수가 보여지면서 $1$ 이상 $N$ 이하가 되도록 바꿔서 사람들을 헷갈리게 할 예정이다. 치르보기를 사랑하는 모임의 회원인 당신은 호석 빌런의 행동을 미리 파악해서 혼쭐을 내주고자 한다. 현재 엘리베이터가 실제로는 $X$층에 멈춰있을 때, 호석이가 반전시킬 LED를 고를 수 있는 경우의 수를 계산해보자.

입력
N, K, P, X$ 가 공백으로 구분되어 첫째 줄에 주어진다.

출력
호석 빌런이 엘리베이터 LED를 올바르게 반전시킬 수 있는 경우의 수를 계산해보자.

제한
1 ≤ X ≤ N < 10^K$
1 ≤ K ≤ 6 $ 
1 ≤ P ≤ 42 $ 

🤔 접근

1. n이 크지 않으니 1부터 n까지 가능 여부를 전부 따져보자
2. 각 문자 간 필요한 반전 수를 테이블에 저장해두자.
3. p 이상으로 반전 시킨 이후에도 불필요한 연산이 계속됨.
4. 재귀함수를 이용하여 가능한 경우만 탐색

💻 내 코드

import sys


def dfs(index, p, new):
    global x, k, rst, n

    if index == k:
        if new != x and new.count('0') != len(new):
            rst += 1
        return
    for i in range(10):
        if (table[int(x[index])][i] <= p) and (new + str(i) <= n):
            dfs(index + 1, p - table[int(x[index])][i], new + str(i))


n, k, p, x = sys.stdin.readline().split()
k = int(k)
p = int(p)
if len(x) < k:
    x = '0' * (k - len(x)) + x
rst = 0

table = [[0, 4, 3, 3, 4, 3, 2, 3, 1, 2], #0
        [4, 0, 5, 3, 2, 5, 6, 1, 5, 4], #1
        [3, 5, 0, 2, 5, 4, 3, 4, 2, 3], #2
        [3, 3, 2, 0, 3, 2, 3, 2, 2, 1], #3
        [4, 2, 5, 3, 0, 3, 4, 3, 3, 2], #4
        [3, 5, 4, 2, 3, 0, 1, 4, 2, 1], #5
        [2, 6, 3, 3, 4, 1, 0, 5, 1, 2], #6
        [3, 1, 4, 2, 3, 4, 5, 0, 4, 3], #7
        [1, 5, 2, 2, 3, 2, 1, 4, 0, 1], #8
        [2, 4, 3, 1, 2, 1, 2, 3, 1, 0]] #9


dfs(0, p, '')
print(rst)

💻 1차 시도 (시간초과)

from collections import deque
n, k, p, x = map(int, input().split())
data = [
		[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]
        ]

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

for i in range(10):
    for j in range(10):
        count = 0
        for d in range(7):
            if data[i][d] != data[j][d]:
                count += 1
        table[i][j] = count

x = deque(list(str(x)))
for n in range(k-len(x)):
    x.appendleft("0")


rst = 0
for num in range(1, n+1):
    count = 0
    num = deque(list(str(num)))
    for n in range(k-len(num)):
        num.appendleft("0")
    for i in range(k):
        a = int(x[i])
        b = int(num[i])
        count += int(table[a][b])
    if count <= p:
        rst += 1

print(rst-1)

💻 2차 시도 (정답)

n, k, p, x = map(int, input().split())

table = [[0, 4, 3, 3, 4, 3, 2, 3, 1, 2], 
		[4, 0, 5, 3, 2, 5, 6, 1, 5, 4], 
        [3, 5, 0, 2, 5, 4, 3, 4, 2, 3], 
        [3, 3, 2, 0, 3, 2, 3, 2, 2, 1], 
        [4, 2, 5, 3, 0, 3, 4, 3, 3, 2], 
        [3, 5, 4, 2, 3, 0, 1, 4, 2, 1], 
        [2, 6, 3, 3, 4, 1, 0, 5, 1, 2], 
        [3, 1, 4, 2, 3, 4, 5, 0, 4, 3], 
        [1, 5, 2, 2, 3, 2, 1, 4, 0, 1], 
        [2, 4, 3, 1, 2, 1, 2, 3, 1, 0]]

x = list((k-len(list(str(x)))) * "0" + str(x))

rst = 0
for num in range(1, n+1):
    count = 0
    num = list((k-len(list(str(num)))) * "0" + str(num))
    for i in range(k):
        a = int(x[i])
        b = int(num[i])
        count += table[a][b]
    if count <= p:
        rst += 1

print(rst-1)

👍 제출