반응형
https://www.acmicpc.net/problem/1311
각 사람이 일을 선택하는 모든 순서 상황의 최솟값을 구해주었습니다.
예를 들어, 세 개의 비트가 010 이라면 첫 번째 사람이 두 번째 일을 선택한 상황입니다.
dp[i] = 비트를 나타내는 수가 i일 때(켜진 비트들은 이미 선택한 일), 남은 비트(일)들을 다 선택하는 최소 비용을 저장해줍니다.
N의 범위는 1이상 20이하이므로, 20명의 사람이 20명의 일을 선택한 것을 표시하기 위해선 20비트가 필요합니다.
#include <iostream>
#include <algorithm>
#define INF 2147483647
using namespace std;
int n, d[20][20], dp[1 << 20] = { 0 };
int dfs(int idx, int v) {
if (idx == n) return 0;
if (dp[v] != 0) return dp[v];
dp[v] = INF;
for (int i = 0; i < n; i++) {
if (v & (1 << i)) continue; // 이미 선택한 일
dp[v] = min(dp[v], dfs(idx + 1, v | (1 << i)) + d[idx][i]);
}
return dp[v];
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &d[i][j]);
}
}
printf("%d", dfs(0, 0));
}
반응형
'Algorithm' 카테고리의 다른 글
백준 2631 : 줄 세우기 (0) | 2021.11.18 |
---|---|
백준 2098 : 외판원 순회 (0) | 2021.11.18 |
백준 1477 : 휴게소 세우기 (0) | 2021.11.18 |
백준 9184 : 신나는 함수 실행 (0) | 2021.11.18 |
백준 1932 : 정수 삼각형 (0) | 2021.11.18 |