[Algorithm]Baekjoon 1311 :: 할 일 정하기 1

https://www.acmicpc.net/problem/1311

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int maxNum = 0x3f3f3f3f;
int n;
int arr[21][21] = { 0 };
int dp[22][1 << 19] = { 0 }; // 비트는 20개만 필요.
 
int DFS(int workerIndex, int state)
{
    int& result = dp[workerIndex][state];
    if (result != maxNum) return result;
    if (state == (1 << n) - 1) return 0;
 
    for (int i = 0; i < n; ++i) // 작업 선택.
    {
        if ((state & (1 << i)) != 0) continue;
 
        result = min(result, DFS(workerIndex + 1, state | (1 << i)) + arr[workerIndex][i]);
    }
 
    return result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    memset(dp, 0x3f, sizeof(dp));
 
    cout << DFS(0, 0);
}
 
 
 

 

문제를 보자 그냥 비트마스킹이 떠올랐다.

각 작업당 한명씩만 배정되어야 하고, 매 탐색마다 어떤 작업이 이미 할당되었는지 빠르게 파악해야하기 때문이다.

dp테이블은 dp[작업자수][비트개수만큼의 정수크기] 이다.

이 문제에서 n은 최대 20이니, 비트는 20개만 필요하다. 그렇기 때문에 1 << 19로 표현했다.

1 << 19인 이유는, 20번째 비트가 1일 경우 10진수로 1 << 19이다.

그러니 코드로 '20번째 비트를 1로 바꾼다~' 라는것을 작성하려할 경우, 배열인덱스가 20번째 비트가 1일경우의 숫자까지 표현해야 하니 1 << 19로 하는 것이다.

 

최종적으로 모든 비트를 킨다면, 해당 수는 십진수로 (1 << n) -1 이 된다.

그렇기 때문에 state가 해당 값이 되면, 모든 작업을 완료했다고 판단하고 0을 리턴한다.