언뜻 보면 비트마스킹 없어도 평범하게 풀 수 있어보인다.
DP 템플릿에 맞춰 기저 사례 찾고, 인자 찾고, 문제 분할하고, 점화식 찾고,,
그런데 뭔가 이상하다. 사람 인덱스가 인자인 것은 확실한데 이것만으로는 문제를 분할할 수 없다. 인자가 하나 더 있는데 대체 뭘까..
당신은 침착하게 앞서 배운 인자의 조건을 되짚는다.
문제를 분할했을 때 같은 인자를 가지는 부분 문제는 반드시 같은 답을 도출할 것
발상 1
가장 먼저 떠올릴 법한 발상은 백트래킹 단원에서 했던 것 처럼 일의 배정 여부를 체크해가며 모든 사람들에게 일을 배정하고 마지막에 비용 합계를 체크하는 방법이다. 이 방법은 말 그대로 방법을 전부 시도하게 되므로 탐색해야하는 경우의 수가 이다. 의 최댓값이 이므로 최대 회의 연산을 하게 된다. 점화식을 굳이 세울 필요가 없다. 이 발상은 여기서 이미 탈락이다.
발상 2
두번째 발상의 핵심은 번째 사람까지의 일 배정이 확정되었을 때 나머지 사람까지 배정하는 최소 비용은 고정된다는 점이다.
어떻게 일을 배정하던지 번째 사람까지 같은 일들이 배정되었다면 나머지 번째 사람까지의 배정은 2번 탐색할 필요없이 저장된 최소 비용을 활용할 수 있다.
재귀적으로 생각해보면 더 쉽게 이해할 수 있다.
일이 어떤 사람에게 배정되었을 때 그 일과 사람이 목록에서 사라진다고 생각해보자.
그러면 나머지 일과 사람에 대해서 최소 비용을 찾는 재귀 구조가 된다.
전체 문제의 최소 비용은 하나밖에 존재할 수 없으므로 재귀 구조의 부분 문제들도 모두 최소 비용은 하나일 수 밖에 없다.
일 배정 상태를 비트 마스크로 표현해 인자로 추가하면 점화식을 수월하게 세울 수 있다.
의 최댓값이 20이므로 이고 사람 인덱스 최댓값이 이므로 배열 최대 수는 이다. int배열로 했을 때 약 83MB이다. 문제 메모리 제한이 512MB 이므로 메모리 제한도 널널하게 만족시킬 수 있다.
점화식
점화식에서 는 이진수 or 연산을 의미한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<vector<int>> arr, dp;
int r(int x, int st) { // x : 사람 인덱스 st : 일 배정 상태 비트 마스크
if (dp[x][st] != -1) return dp[x][st]; // 같은 사람까지의 일 배정이 같다면 저장된 최소 비용 리턴
int mn = 21e8;
for (int i = 1; i <= n; i++) {
if ((st & (1 << (i - 1))) == 0) { // 아직 배정되지 않은 일인 경우
int s = r(x + 1, st | (1 << (i - 1))) + arr[x][i];
mn = mn < s ? mn : s;
}
}
return dp[x][st] = mn;
}
int main()
{
cin >> n; arr = vector<vector<int>>(n + 1, vector<int>(n + 1)); dp = vector<vector<int>>(n + 2, vector<int>(1 << n, -1));
dp[n + 1][(1 << n) - 1] = 0; // 기저 사례 : 모든 사람들에게 일이 배정된 경우 비용은 0
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> arr[i][j];
}
}
cout << r(1, 0);
return 0;
}