백준 [1311] 할 일 정하기 1

문제 설명

풀이

dp[현재 사람][이전까지 수행한 일의 상태] = 현재 일의 상태까지의 최솟값

이 문제는 비트마스크와 dp를 이용하여 풀이할 수 있다. 이전까지 수행한 일의 상태를 0011 -> 1, 2번이 일을 한 상태와 같이 비트를 이용하여 상태를 표시한다.

코드

#include <cstdio>
#include <cstring>

int d[22][22];
int dp[22][1 << 19];
int N;

int min(int a, int b) { return a > b ? b : a; }

int dpf(int cur, int state) {
    int &ret = dp[cur][state];
    //모든 일을 한 상황 ex) n = 3일때 1000 - 1 = 0111
    if (state == (1 << N) - 1) return 0;
    if (ret != -1) return ret;
    int ans = 1e9;
    for (int i = 0; i < N; i++) {
        if ((state & (1 << i)) == 0) {
            ans = min(ans, dpf(cur + 1, state | (1 << i)) + d[cur][i]);
        }
    }
    return ret = ans;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &d[i][j]);
    memset(dp, -1, sizeof(dp));
    printf("%d", dpf(0, 0));
}