[코딩테스트][백준] 🔥 백준 1102번 "발전소" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 50분

import sys

input = sys.stdin.readline

N = int(input())
costs = [list(map(int, input().split())) for _ in range(N)]
ofoff = list(input().strip())
P = int(input())

INF = 36 * 16

max_mask = 1 << N
dp = [-1] * max_mask

initial_mask = 0
initial_num = 0
for i in range(N):
    if ofoff[i] == 'Y':
        initial_mask |= (1 << i)
        initial_num += 1

def dfs(mask):
    if dp[mask] != -1:
        return dp[mask]

    num = bin(mask).count('1')

    if num >= P:
        dp[mask] = 0
        return 0

    min_cost = INF

    for i in range(N):
        if not (mask & (1 << i)):
            min_next_cost = INF

            for j in range(N):
                if mask & (1 << j):
                    min_next_cost = min(min_next_cost, costs[j][i])

            if min_next_cost == INF:
                continue

            new_mask = mask | (1 << i)
            cost_i = min_next_cost + dfs(new_mask)

            min_cost = min(min_cost, cost_i)

    dp[mask] = min_cost
    return dp[mask]

if initial_num >= P:
    print(0)
else:
    result = dfs(initial_mask)

    print(result if result < INF else -1)

💡 비트마스킹과 DP로 발전소 문제 정복! 🚀

DFS를 DP로 최적화시킬줄 알고 비트마스크를 다룰 줄 안다면 플레5 문제 치고 쉽게 접근할 수 있는 문제이다.

먼저 발전소가 켜져 있는데로 비트에 기록하고 이것의 갯수를 기록해 놓는다. 이미 요구하는 갯수만큼 켜져있는 경우가 있기 때문에 이미 그 수의 이상으로 켜져 있다면 0을 출력하면 된다. 그렇지 않을 경우에는 DFS를 통해 비용을 추적한다. 최대 비용은 최대 비용이 36이고 발전소의 갯수가 16개 이하이므로 36*16으로 최댓값을 잡고 시작한다.

먼저 dp의 모든 값에 대해서 visited의 비트로 추적할 수 있기에 이를 이용하면 쉽다. dp의 갯수는 그렇기에 모든 비트의 경우의 수로 둘 것이기에 이 갯수만큼 두면 된다. 만약 현재 visited에 대한 최소값이 찾아져 있다면 현재 값을 반환한다. 그리고 현재 비트에서 1의 수 보다, 즉 켜져 있는 발전소의 값의 이미 P개 이상이라면 추가 비용이 없으므로 0을 반환한다.

이제 나머지 경우에 대해서다. 안켜져 있는 모든 발전소에 대해서 켜져 있는 모든 발전소로부터의 최소 비용을 먼저 구한다. 이 비용이 현재 상태에서의 발전소를 키는 비용이 되고 이 비용에 앞으로 추적할 비용을 dfs한 다음 더해주면 된다. 그렇게 현재 비트에서의 최소 비용을 구해서 dp에 넣어주면 된다.

이렇게 Python로 백준의 "발전소" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊