phnml1
⌕
AlgorithmAlgorithm백준golddfs

[백준 gold 5] 빌런 호석

Published2024.08.10
Read Time6 min read

[gold 3] 빌런 호석

문제 설명

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

1.png

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

2.png

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

입력

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

출력

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

접근 방법

숫자에 따른 LED를 먼저 구현하기 위해,

그림과 같이, 각 LED의 위치에 번호를 매겨, 배열안에 그 번호가 있으면 불이 켜져있는 것으로, 없다면 불이 꺼져 있는 것으로 표현하였다. 이미지 설명

그림처럼 0을 표현하면 3번자리를 제외한 모든 번호가 켜져있으므로, [0,1,2,4,5,6]으로 표현 할 수 있다.

각 번호를 이와 같이 바꾸어 numbers 배열에 저장하면, 이와 같다.

numbers  = [[0,1,2,4,5,6],[2,5],[0,2,3,4,6],[0,2,3,5,6],[1,2,3,5],[0,1,3,5,6],[0,1,3,4,5,6],[0,2,5],[0,1,2,3,4,5,6],[0,1,2,3,5,6]];

이후 만일 현재 번호와 비교할 번호의 LED를 비교하기 위해 서로의 차집합을 더해서 두 번호가 서로를 비교했을 때, 가지고 있는 혹은 없는 번호의 개수를 구한다.

cur_count  =  len(list(cur.difference(compare))) +  len(list(compare.difference(cur)));

이와 같은 방식으로 반전시킬 LED의 개수를 구하고, dfs를 활용하여 x의 모든 자릿수를 순회하여 p보다 작거나 같게 LED를 반전하면서, n보다 번호가 작거나 같다면 result를 1 증가 시킨다.

전체코드는 다음과 같다.

import sys;
input = sys.stdin.readline;

n,k,p,x = map(int, input().split());
result = 0;
numbers = [[0,1,2,4,5,6],[2,5],[0,2,3,4,6],[0,2,3,5,6],[1,2,3,5],[0,1,3,5,6],[0,1,3,4,5,6],[0,2,5],[0,1,2,3,4,5,6],[0,1,2,3,5,6]];

x = list(str(x));
if len(x) != k:
	# k 보다 자릿수 x가 자릿수가 작다면 작은 만큼 앞에 0을 채워주어야 한다.
    for _ in range(k-len(x)):
        x.insert(0,'0');
        
def dfs(index,count,st):
    global result;
    if count>p:
        return;
    if index == k:
        if 0<count<=p and 0<int(st)<=n:
            result += 1;
        return;
    cur = set(numbers[int(x[index])]);
    for i in range(len(numbers)):
        compare = set(numbers[i]);
        cur_count = len(list(cur.difference(compare))) + len(list(compare.difference(cur)));
        if count + cur_count <=p:
            dfs(index+1,count + cur_count,st + str(i));
dfs(0,0,'');
print(result);

느낀 점

사실 이 문제와 관련하여 다른 풀이도 많이 찾아보았고, 더욱 시간이 적게 걸리는 풀이도 많았어서 시간 초과는 나지 않았지만 다소 비효율적인 풀이였다는 생각이 들었다.

또한 제한 사항중 또한 반전 이후에 디스플레이에 올바른 수가 보여지면서 1 이상 N 이하가 되도록 바꿔서 사람들을 헷갈리게 할 예정이다.를 못봐서 계속 0<=int(st)<=n로 조건을 설정해놓고 헤맸었다. 문제의 조건을 유심히 보는 습관을 들여야 함을 다시한번 느낀다.