BOJ 1311 할 일 정하기 1

1 개요

BOJ 1311 할 일 정하기 1

• 백준 온라인 저지 1311번 문제
• BOJ 40단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N;
int D[20][20];
int dp[20][1 << 21];
int INF = INT_MAX/2;

int dfs(int x, int visited) {
	if(visited == (1<<N)-1) return 0;
	if(dp[x][visited] != -1) return dp[x][visited];
	dp[x][visited] = INF;
	for (int i=0; i<N; i++) {
		if(visited & (1<<i)) continue;
		dp[x][visited] = min(dp[x][visited], dfs(x+1, visited | (1<<i)) + D[x][i]);
	}
	return dp[x][visited];
}

int main() {
    cin >> N;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> D[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0);
}