문제
풀이
비트마스크 활용 문제이다. 비트마스크를 이용한 dp로 완전탐색을 하는 문제로서 많이 출제되는 문제이다. 먼저 pow(2,N)개의 dp배열을 선언한다. 이 dp배열은 N개의 일들이 각각 행해졌는지 그렇지 않은지의 정보를 담은 배열이다. 예를 들어, N이 3일 때, 011은 2번째 일은 행해지지 않고, 나머지 0, 1번째 일은 행해진 경우이다. dp를 활용하기 위해 먼저 INF로 초기화를 해놓는다. 그 이후, 이중 for문을 이용하는데, 가장 바깥 loop는 할당된 일의 정보를 담고 있다. 그 안에 있는 j의 경우는 이 일을 할당했을 때를 의미하게 된다. 그 사이에 있는 x의 값은 i의 2진수 값에서 1이 몇개인지를 세는 것으로, 이제 몇번째 사람에게 일을 시켜야 하는지를 알기 위함이다. 결국. j번째 일을 할당한 경우의 dp의 값은 최소값을 알아내야하므로, j번째 일이 할당되지 않았다면 기존에 저장되있던 해당 인덱스 dp값과 j번째 일을 하지 않은 인덱스의 dp값 + x번째 사람이 j번째 일을 했을 때 드는 cost를 합친 것을 비교하여 작은 값으로 새로 갱신하면 되는 문제이다. 비트마스크를 통한 완전 탐색 문제를 잘 익혀두자.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <cmath>
#define INF 987654321
using namespace std;
int count_bit(int num){
int cnt = 0;
while(num){
cnt += (num & 1);
num >>= 1;
}
return cnt;
}
int main(){
int N;
scanf("%d", &N);
vector<int> testcase[N];
for(int i = 0; i<N; i++){
for(int j = 0 ; j<N; j++){
int tmp;
scanf("%d", &tmp);
testcase[i].push_back(tmp);
}
}
vector<int> dp;
for(int i = 0 ; i<pow(2,N); i++){
dp.push_back(INF);
}
dp[0] = 0; // 모두 일을 안한 경우는 당연히 0
for(int i = 0 ; i<pow(2,N); i++){
int x = count_bit(i);
for(int j = 0; j<N; j++){
if(!(i & (1<<j))){ // j번째 일이 할당 되어지지 않은 경우
dp[i | (1<<j)] = min(dp[i | (1<<j)], dp[i] + testcase[x][j]);
// j번째 일이 할당이 추가된 경우는 기존의 경우와 j번째 일이 할당되지 않은 경우에 x번째 사람이 j번째 일을 하는 경우를 합한 경우와 비교하여 작은 것으로 할당
}
}
}
printf("%d\n", dp[dp.size()-1]);
}
