(1311) 할 일 정하기 1

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

단계별로 풀어보기

40단계(동적 계획법 3) 2번째

 

 

 

비스마스크를 이용한 DP문제다

dp[state]는 state 상태에서 남은 일을 추가로 하기 위한 비용의 최소값이다. state에서 n번째 비트는 n번 일을 의미하며 비트값이 1이면 한 일, 0이면 아직 하지 않은 일을 의미한다.

state 상태에서 i번 사람이 j번 일을 추가로 하면 d[i][j]가 추가되므로 dp[state]와 dp[state|(1<<j)]+d[i][j]를 비교해 값을 갱신해주고, i를 1부터 N까지 순회하며 진행하면 된다.

 

비스마스크를 이용한 DP는 재귀와 DP에 대해 잘 알아야 하는 굉장히 어려운 파트이다.

처음 배울 땐 이해 못했는데 나중에 실력이 쌓이고 Digit DP라는 것에 대해 배울 때 비트마스크 DP에 대해서도 이해하게 되었는데 설명하기가 굉장히 어렵다. 본인이 코드나 갱신 과정을 분석하면서 이해하는 것이 최선이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define INF 200001

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector d(n, vector<int> (n));
  vector<int> dp(1<<n, -1);
  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin >> d[i][j];
    }
  }
  
  auto func= [&](auto self, int now, int state) -> int {
    if(now==n)  return 0;
    
    int &ret= dp[state];
    
    if(ret!=-1)  return ret;
    
    ret= INF;
    
    for(int i=0;i<n;i++){
      if(state&(1<<i))  continue;
      
      ret= min(ret, self(self, now+1, state|(1<<i))+d[now][i]);
    }
    
    return ret;
  };
  
  cout << func(func, 0, 0);
  
  return 0;
}