백준 1311 - 할 일 정하기 1

www.acmicpc.net/problem/1311

 

어렵지 않은 비트마스크 dp이다.

 

다음 dp테이블을 정의하고 탑 다운 dp로 풀면 된다.

 

dp[i] = 비트마스크 i의 조합으로 일을 할당했을 때 비용의 최솟값

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
int ar[20][20];
int dp[1 << 20];
 
int memo(int bt, int idx);
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n;
 
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> ar[i][j];
    
    memset(dp, -1, sizeof dp);
    int res = 1e9;
 
    for (int i = 0; i < n; ++i)
        res = min(res, ar[0][i] + memo(1 << i, 1));
 
    cout << res;
}
 
int memo(int bt, int idx)
{
    if (idx == n)
        return 0;
    
    int &ret = dp[bt];
 
    if (ret != -1)
        return ret;
    
    ret = 1e9;
 
    for (int i = 0; i < n; ++i)
        if (!(bt & (1 << i)))
            ret = min(ret, ar[idx][i] + memo(bt | (1 << i), idx + 1));
 
    return ret;
}