[BOJ 1311] 할 일 정하기 1

문제

---

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

풀이

---

일을 배정받은 사람 정보와 배정된 일의 정보 각각을 비트마스크로 관리하면 DP 테이블의 크기가 2 ** 40으로 TLE를 받는다.

외판원 순회 문제도 그렇고 N * 2 ** N 크기의 DP 테이블을 자주 봤으니 끼워 맞춰보자.

1번 사람부터 차례로 일을 배정하거나, 1번 일부터 차례로 배정시키면 해결된다.

그런데 2 * 2 ** N 크기의 DP 테이블 + Bottom-Up 방식으로 문제를 풀 수 있다.

dp[사람_mask]에 [결과, 일_mask] 이런 식으로 담으면 가능하다.

코드

---

import sys

n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [(0, 0)] * 2 ** n

for k in range(1, 2 ** n):
    res = float('inf')
    mask = 0
    for i in range(n):
        if k & (1 << i):
            temp, sub_mask = dp[k | (1 << i)]
            sub_res = float('inf')
            idx = 0
            for j in range(n):
                if (not sub_mask & (1 << j)) and (sub_res > board[i][j]):
                    sub_res = board[i][j]
                    idx = j

            sub_res += temp
            sub_mask |= (1 << idx)

            if res > sub_res:
                res = sub_res
                mask = sub_mask

    dp[k] = (res, mask)

print(dp[-1][0])