백준 / 1311 할 일 정하기 1 C++

www.acmicpc.net/problem/1311

1311번: 할 일 정하기 1

비트마스킹을 이용한 다이나믹 프로그래밍 문제입니다. 비트마스크로 해당 index의 비트를 껐다 켰다를 반복해 일을 한지 안 한지를 체크하면 됩니다.

 

처음 접하는 유형이라 정확히 알아보기 위해 해당 알고리즘을 검색하였는데 비슷한 예제로 설명한 글을 읽어 어렵지 않게 풀었습니다. 

 

( 참고 : zzonglove.tistory.com/43 )

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

int n;
vector<int>work[21];
vector<int>dp;
int inf = 987654321;

void make_works()
{
	cin >> n;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++) {
			int w;
			cin >> w;
			work[i].push_back(w);
		}
	}
}

// bitmask 이용한 dp (초기화 : inf)
// 수행한 작업(i)을 n 길이의 bit의 1로 켠다.
// i번째 비트 켜기 : bit | (1<<i)
// i번째 비트 끄기 : bit & ~(1<<i)
// i번째 비트 켜져 있는 지 확인 : bit & (1<<i)
// dp[bit | (1<<i)] = min(dp[bit | (1<<i)], dp[bit]+work[x][i])
// x : bit에 있는 1의 개수

int count_bit(int num)
{
	int cnt = 0;
	while (num) {
		cnt += (num & 1);
		num >>= 1;
	}
	return cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	make_works();
	
	for (int i = 0; i < pow(2, n); i++) {
		dp.push_back(inf);
	}
	dp[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))) {
				dp[i | (1 << j)] = min(dp[i | (1 << j)], dp[i] + work[x][j]);
			}
		}
	}

	cout << dp[dp.size() - 1];
}