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를 올바르게 반전시킬 수 있는 경우의 수를 계산해보자.

---

많은 시행 착오가 있었다.

일단 기본 알고리즘은 각 숫자를 비트(이진수)로 표현하고 차이를 계산하여 횟수를 줄여가면서 찾는 방법.

N과 X의 빈 부분을 0으로 채웠다.

함수에 자릿수, 횟수, 현재 숫자를 넘겨준다.

층 계산을 카운트 전에 해야한다. 

밖에서 할 경우 겹치는 경우를 다 넘기게 된다.

import sys

# 층, 자리수, 반전 횟수, 현재 층
N, K, P, X = sys.stdin.readline().split()

K = int(K)
P = int(P)

cknum = int(N)
renum = int(X)
N = [0]*(K-len(N)) + list(map(int,list(N)))
X = [0]*(K-len(X)) + list(map(int,list(X)))


num = [0b1110111,0b0010010,0b1011101,0b1011011,0b0111010,0b1101011,0b1101111,0b1010010,0b1111111,0b1111011]

# 카운트
cnt = 0
# 자릿수
idx = 0
# 숫자
number = 0
# 앞자리 부터
def led(idx,P,number):
    global cnt
    # 0부터 9까지 확인
    for i in range(10):
        # K넘으면 리턴
        if idx > K-1:
            return

        # 해당 층수 넘으면 패스
        if cknum < number + i*(10**(K-1-idx)):
            return
        else:
            # 차이 계산
            chi = list(bin(num[X[idx]] ^ num[i])[2:]).count("1")
            # 횟수보다 많이 한다면 넘기기
            if P - chi < 0:
                continue

            # 자릿수가 마지막이면 숫자 확인
            if idx == K-1:
                # 0이나 현재 층 수는 패스
                if 0 == number + i*(10**(K-1-idx)) or renum == number + i*(10**(K-1-idx)):
                    continue
                #print("a",number + i*(10**(K-1-idx)))
                cnt += 1
                continue
            # 다 통과하면 자릿수는 늘리고 횟수는 줄이고 숫자는 해당 숫자로 넘긴다
            led(idx+1,P - chi,number + i*(10**(K-1-idx)))

led(idx,P,number)
print(cnt)