1311. 할 일 정하기 1

단계별로 풀어보기 따라가는 중.

1311번: 할 일 정하기 1

---

$N$명의 사람과 $N$개의 일이 있다. $i$번 사람이 $j$번 일을 할 때의 비용 $D[i][j]$가 주어질 때, 비용을 최소로 하면서 각 사람에게 하나의 일을 할당해 보자.

 

딱 봐도 dp이고, 선택된 일의 집합을 표현해야 하므로 비트마스크 dp를 적용할 수 있다. 마침 $N$이 20으로 매우 작기도 하고.

 

현재 남아있는 일의 집합을 $j$(비트마스크)일 때 $i$번 사람에게 일을 할당하여 얻을 수 있는 비용의 최솟값을 $dp[i][j]$로 정의할 수 있다. 수식으로 표현하면 다음과 같다.

 

$dp[i][j] = \min(D[i][work] + dp[i+1][j - 2^{work}]) ~\forall~ work \in j$

 

그런데 더 빠르게 풀 수도 있다. 위의 식을 대부분 DFS DP로 구현할 텐데, DFS에서 $i$는 항상 1씩 증가하므로 굳이 $dp$에 $i$를 포함할 필요가 없다. 정확히는 상태 집합에 $i$를 포함할 필요는 없다는 말이다.

 

따라서 상태 집합은 남아있는 일의 집합 $j$만으로 충분하다. 의사코드는 다음과 같다.

// depth: 일을 할당할 사람의 번호
// bitmask: 현재 남아있는 일의 집합 (비트마스크)
solve(depth, bitmask):
    if bitmask < 0:
        return INF
    if depth == 0:
        return 0
    
    if dp[bitmask] != -1:
        return dp[bitmask]
    
    for work in j:
        ret = min(D[depth][work] + solve(depth+1, bitmask - (1 << work)))
    dp[bitmask] = ret
    return ret

 

---

이걸로 solved.ac 플1 달성.

번외: $N$이 커지면?

$N$이 50만 돼도 비트마스크를 쓸 수 없다. 예를 들어 이런 문제는 어떻게 풀어야 할까?

14216번: 할 일 정하기 2

Hungarian Algorithm을 사용하면 $O(N^{3})$ 시간에 해결할 수 있다. 한번 공부해 봐야겠다.