백준 1311번 할 일 정하기 1 - C++ 풀이

---

 

1. dp(idx, mask): 사람들의 상태가 mask일 때, idx~마지막 일까지 수행하기 위한 최소 비용
2. dp(idx, mask) = min(i번 사람에게 맡겼을 때의 비용 + dp(idx+1, mask | (1 << i))

 

1. dp(idx, mask): 사람들의 상태가 mask일 때, idx~마지막 일까지 수행하기 위한 최소 비용

 한 사람당 1개의 일만 맡을 수 있다. 비트 마스크를 이용해 i번 사람이 이미 맡은 일이 있는지 여부를 i번 비트로 나타낸다. 그리고 위와 같이 dp를 정의하자.

 

2. dp(idx, mask) = min(i번 사람에게 맡겼을 때의 비용 + dp(idx+1, mask | (1 << i))

 idx번째 일을 누군가에게는 맡겨야 한다. 0번 사람부터 (N-1)번 사람까지 순회하면서 비용이 최소가 되는 경우를 구한다. 이때 mask를 활용해서 이미 다른 일을 맡고 있는 사람은 스킵한다.

 

반응형

---

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 987654321;

int N;
int cost[20][20];
int cache[20][1 << 20];

// dp(idx, mask)
// :사람들의 상태가 mask일 때 idx~마지막 일까지 수행하기 위한 최소 비용
int dp(int idx, int mask) {
    if (idx == N) return 0;
    
    int& ret = cache[idx][mask];
    if (ret != -1) return ret;
    
    ret = INF;
    for (int i=0; i<N; i++) {
        if ((mask & (1 << i)) != 0) continue;
        ret = min(ret, cost[i][idx] + dp(idx+1, mask|(1 << i)));
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> N;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> cost[i][j];
        }
    }
    
    cout << dp(0, 0);

    return 0;
}