[백준] 22251: 빌런 호석 python 구현 / 완전 탐색

문제

풀이

예시:

• 입력: 9 1 2 5
• LED를 2개까지 바꿀 수 있을 때, 5층 → 3층, 6층, 8층, 9층

처음에는 5층을 변환해서 가능한 숫자가 있다면 개수를 세려고 했다.

그렇게 하면 경우의 수가 너무 많아짐..! 한 자리 수가 아니고 K=6이라 6자리 수 일경우 바꿀 수 있는 P를 분배하는 방법 부터해서 계산이 너무 복잡해졌다..

그래서 정답을 먼저 확인한 후 완전탐색으로 코드를 바꾸었다. 

 

그리하여 풀이는 아래와 같다.

1. 디지털 숫자를 0과 1로 표현한다 (ex) 0 → 1 1 1 1 1 1 0, 중간 빼고 다 켜짐)
2. 현재의 층을 0과 1로 표기한다.
   1. K에 맞춰 앞을 0으로 표기해준다. (K=4, X=5 → "0005")
   2. 이후 1번과 동일하게 현재의 층을 0과 1 로 표기한다.
3. 1층부터 N층까지 완전 탐색을 실시하며 현재 층에서 n번째 층으로 변환이 가능한지 확인한다.
   1. 탐색 중인 n번째 층을 2와 동일한 로직으로 0과 1로 표기한다. 
   2. 각 자리의 숫자가 변하기 위해 필요한 개수를 세고 이의 총 합이 P개 이하라면 변환할 수 있는 것으로 보고 결과값에 추가한다.

 

그런데 시간초과 문제로 인해 Python 3로는 해결하지 못하였다ㅠㅠ

pypy3로만 해결한 코드를 공유한다.

 

CODE

N, K, P, X = map(int, input().split())

num2digital = {'0': [1, 1, 1, 1, 1, 1, 0],
               '1': [0, 1, 1, 0, 0, 0, 0],
               '2': [1, 1, 0, 1, 1, 0, 1],
               '3': [1, 1, 1, 1, 0, 0, 1],
               '4': [0, 1, 1, 0, 0, 1, 1],
               '5': [1, 0, 1, 1, 0, 1, 1],
               '6': [1, 0, 1, 1, 1, 1, 1],
               '7': [1, 1, 1, 0, 0, 0, 0],
               '8': [1, 1, 1, 1, 1, 1, 1],
               '9': [1, 1, 1, 1, 0, 1, 1]}

# 1 ~ N개의 층을 완전 탐색한다.
# P개 이내의 표시등을 반전시켜 해당 숫자를 만들 수 있다면 !

X = str(X).zfill(K) # K=4, X=5 -> 0005
x_transform = [num2digital[x] for x in X]

possible_num = 0
for n in range(1, N+1):
    elevator = str(n).zfill(K)
    ele_transform = [num2digital[e] for e in elevator]

    diff_cnt = 0
    for x, e in zip(x_transform, ele_transform):  # 1~6개
        for i, j in zip(x, e):
            if i != j:
                diff_cnt += 1
        if diff_cnt > P:
            break

    if diff_cnt <= P and diff_cnt > 0:
        possible_num += 1

print(possible_num)