[BOJ] 백준 1311. 할 일 정하기 1 (Gold I)

간단한 bitmask dp이다. 

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

1311번: 할 일 정하기 1

난 dp에 꽤 약한 편이라 bitmask+dp 문제는 플레 문제를 풀 엄두가 나지 않았다.

기본적인 bitmask_dp 문제들이 Gold I이어서 G1문제들을 손쉽게 풀 수 있을 때쯤 플레를 도전해보지 않을까 싶었는데,

이 문제를 통해 이제 나도 bitmask_dp임을 파악할 수 있는 실력과, 그 때 해결할 수 있는 능력이 꽤 괜찮음을 파악하게 됐다.

 

굉장히 심리적으로 안정되게 손쉽게 해결할 수 있었다.

이제 슬슬 #1014번 컨닝, #1086 박성원 문제들도 한번 눈들여봐야겠다.

---

의식의 흐름 및 해설

누가 어떤 일을 하고 있는지에 따라 dp값이 달라지며, 반드시 한 명은 하나의 일을 해야 하므로 상태를 저장해야 하는 dp이다. 사람 인원은 최대 20명이니까, dp[21][2][2][2]...[2]로 배열을 둘 수도 있지만, bitmask를 이용하여 dp배열을 dp[21][1<<21]로 잡는다면 편리하게 상태를 저장할 수 있는 배열이 된다.

 

bitmask에서

값이 0인지 1인지 파악은 flag&(1<<i)가 1일 때만 값이 1이므로 이 식으로 파악 가능하고,

flag|(1<<i)로 인자로 상태변화를 주어서 넘겨줄 수 있다.

모두 한명씩 일을 맡으면, 모든 일이 다 인원에게 맡겨진 것이므로 상태 인자가 (1<<N)-1이 될 것이다.

---

시행착오

#include <cstring>을 넣지 않으면 컴파일 에러가 뜬다는 것을 망각하고 바로 제출을 넣어 컴파일에러를 띄웠다.

	for (int i = 0; i < N; i++) {
		if (!(flag & (1 << i)))
			ret = min(ret, dp(i + 1, flag | (1 << i)) + a[cur][i]);
	}

또한 위와 같이 dp(cur+1, ...)가 아닌 dp(i+1, ...)로 인자를 넘겨주어,

수많은 인원들에게 일을 배분하는 걸 건너뛰어버리기도 하여 WA를 받기도 하였다.

3
2 3 3
3 2 3
3 3 5
ans: 8

다행히 내가 임의로 만든 위 TC로 2분만에 빠르게 해결하여 AC를 받았다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 21;
const int INF = 0x3f3f3f3f;
int N, a[MAX][MAX], d[MAX][1 << 21];
int dp(int cur, int flag) {
	if (cur >= N)
		return flag == (1 << N) - 1 ? 0 : INF;
	int& ret = d[cur][flag];
	if (ret != -1)
		return ret;
	ret = INF;
	for (int i = 0; i < N; i++) {
		if (!(flag & (1 << i)))
			ret = min(ret, dp(cur + 1, flag | (1 << i)) + a[cur][i]);
	}
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a[i][j];
		}
	}
	memset(d, -1, sizeof(d));
	cout << dp(0, 0) << "\n";
}

---

기본적인 bitmask_dp 문제였다.

예전에 비해 실력이 꽤 늘었음을 확인할 수 있었던 문제였다.

상병 되기 전에 1014번, 1086번도 해결해봐야겠다.