[1311] 할 일 정하기 1

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

1311번: 할 일 정하기 1

<문제>

하나의 사람은 하나의 일만 할 수 있으므로 어떤 사람이 아직 일을 할당받지 못했는지를 비트로 표현한다.

depth와 1<<n을 인덱스로 넣어 메모이제이션 하기위한 2차원 dp를 사용했다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, a[20][20], dp[20][1 << 20];
int f(int d, int bt) {
    if (d == n) return 0;
    if (dp[d][bt]) return dp[d][bt];
    int i;
    dp[d][bt] = INF;
    for (i = 0; i < n; i++) {
        if (bt & (1 << i)) continue;
        dp[d][bt] = min(a[d][i] + f(d + 1, bt | (1 << i)), dp[d][bt]);
    }
    return dp[d][bt];
}
int main(void) {
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) cin >> a[i][j];
    cout << f(0, 0);
    return 0;
}