[백준 🥇5] 22251번 빌런 호석 (Python/파이썬)

1️⃣ 문제

https://www.acmicpc.net/problem/22251

2️⃣ 코드

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

# 자릿수 맞춰주기 
if len(str(x)) < k:
    cx = '0' * (k-len(str(x))) + str(x)   
else:
    cx = str(x)

num = ['1111110', '0110000', '1101101', '1111001', '0110011', '1011011',
       '1011111', '1110000', '1111111', '1111011']
arr = []

for i in range(10):
    arr.append([])
    for j in range(10):
        if i == j:
            arr[i].append(0)
        else:
            d = 0
            for h in range(7):
                if num[i][h] != num[j][h]:
                    d += 1
            arr[i].append(d)


def dfs(dep, cnt, cx):   # 깊이, 남은 반전 가능 횟수, 현재 문자열
    if dep >= len(cx):
        if int(cx) == x:   # 현재 층수와 결과가 같으면 안됨 
            return 0
        elif 1 <= int(cx) <= n:   # 조건에 맞는 경우
            return 1
        else:   # 그외 경우는 불가능 
            return 0

    rst, cur = 0, int(cx[dep])   # 정답, 현재 바꿔줄 숫자 
    for i in range(10):
        if cur != i and (arr[cur][i] <= cnt):   # 남은 반전 가능 횟수보다 필요한 반전 횟수가 작아야 바꿀 수 있음
            dx = cx[:dep] + str(i) + cx[dep+1:]
            rst += dfs(dep+1, cnt-arr[cur][i], dx)

        elif cur == i:
            rst += dfs(dep+1, cnt, cx)

    return rst
            
                
print(dfs(0, p, cx))

3️⃣ 풀이

티어가 골5인데 어떻게 풀어야할지 감이 안와서 살짝 충격먹음😢
찾아보니 파이썬 풀이는 나오지도 않아서 다른분들 C++ 풀이 보고 풀었다
비트마스킹+DFS 문제였다

​

코드 윗부분부터 순서대로 설명하면

1. 문제에 나와있는 것처럼 K=4인데 X=501일 경우, 0501로 0을 앞부분에 더해 자릿수를 바꿔줘야 한다

​

2. num 리스트는 디스플레이의 각 숫자를 문자열 형태로 바꿔준 것이다
   
   이런식으로 불이 들어온 부분은 1, 들어오지 않은 부분은 0으로 해서 각 숫자를 문자열로 바꿀 수 있다!

​

3. arr은 각 숫자를 다른 숫자로 바꿀 때 반전시켜줘야 하는 LED의 개수를 저장한 리스트이다
   아래 사진은 실제 코드에서 arr 리스트를 출력한 사진인데, 문제에서 나온 것처럼 숫자 1을 2로 바꾸려면 총 5개의 LED를 반전시켜야 하므로, arr[1][2]=5인 것을 확인할 수 있다
   난 그냥 단순하게 3중 for문을 사용해서 계산했다
   

​

4. 마지막으로 DFS 함수에 대해 설명하면, 실제 층수(X)의 각 자릿수를 다른 숫자로 바꿔주며 조건에 맞는지 확인한다
   즉, X=35이면 3을 다른 숫자로 바꿔주고, 5를 다른 숫자로 바꿔주며, 결과가 1 이상 48 이하인지 확인하는 것이다 (테케 2번의 경우)
   나머지는 전형적인 DFS 방식이다

​

알고보면 별로 어렵진 않은 문제인데
만약 실제 코테에서 이렇게 나왔을 때 풀 수 있을지는 글쎄요😔