[골드 1] 백준 1311 - 할 일 정하기 1 (파이썬)

분류 : 다이나믹 프로그래밍

링크 : https://www.acmicpc.net/problem/1311

풀이

이 문제는 N * N 크기의 비용 행렬 D가 주어지고, 사람 N명에게 각각 하나의 일을 배정하는데, 각 사람마다 각 일에 대한 비용이 다르다.

각 사람에게 정확히 하나의 일만, 각 일도 정확히 한 사람에게만 배정되도록 하면서 총 비용의 합을 최소화 해야한다.

1. 초기 설정

cache = [[-1] * (2 ** N) for _ in range(N)]

cache[x][mask]는 x번째 사람까지 할당했을 때, mask 상태에서의 최소 비용을 저장한다.

1. 기저 조건

if x == 0:
    for i in range(N):
        if mask == (2 ** i):
            cache[x][mask] = D[x][i]
            return D[x][i]

첫번째 사람에게 일을 한 개만 할당한 경우 해당 비용을 바로 반환한다.

1. 재귀적으로 최소 비용을 계산

for i in range(N):
    if mask & (2 ** i) != 0:
        ret = min(ret, D[x][i] + dp(x - 1, mask - (2 ** i)))

현재 x번째 사람에게 i번째 일을 배정할 수 있는 경우에 대해, 그 비용과 이전 상태의 최소 비용을 더해서 ret를 갱신한다.

1. 결과 반환

return dp(N - 1, (2 ** N) - 1)

사람 N명을 모두 배정한 경우, 모든 일이 사용되었을 때의 최소 비용을 출력한다.

코드

# 백준 1311 - 할 일 정하기 1
# 분류 : 다이나믹 프로그래밍
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]

cache = [[-1] * (2 ** N) for _ in range(N)]
# N * (2 ^ N)
def dp(x, mask) :
    if cache[x][mask] != -1 :
        return cache[x][mask]

    if x == 0 :
        for i in range(N) :
            if mask == (2 ** i) :
                cache[x][mask] = D[x][i]
                return D[x][i]
    
    ret = 1e9
    for i in range(N) :
        if mask & (2 ** i) != 0 :
            ret = min(ret, D[x][i] + dp(x - 1, mask - (2 ** i)))
        
    cache[x][mask] = ret
    return ret
    
print(dp(N - 1, (2 ** N) - 1))