[BAE/<JOON> 문제풀이] 1311. 할 일 정하기 1

www.acmicpc.net/problem/1311

1311번: 할 일 정하기 1

서론 ||

처음에는 기업 투자와 비슷해 보였지만

외판원과 매우 비슷한 문제

 

풀이 ||

일의 상태를 비트마스크로 치환하고 각각의 사람과 일의 상태를 매칭시키며 메모이제이션을 적용하면 풀 수 있다.

 

점화식 || 

외판원 문제와 점화식이 같다.

 

하지만 일을 배정하는데 순서는 관계 없으므로 그냥 단순히 차례대로 배정하며 메모이제이션을 적용해도 무리 없이 풀 수 있다.

 

코드 ||

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

using namespace std;

int dp[21][(1 << 20) - 1];
int complete;
int n;
vector<vector<int>> arr;

int f(int now, int bitm) {
	if (complete == bitm) {
		return 0;
	}
	int& ret = dp[now][bitm];
	if (ret != 0) return ret;
	int mn = 2100000000;
	for (int i = 1; i <= n; i++) {
		if ((bitm & (1 << (i - 1))) == 0) {
			int res = f(now + 1, bitm | (1 << (i - 1)));
			mn = min(mn, res + arr[now][i]);
		}
	}
	return ret = mn;
}

int main()
{
	cin >> n;
	complete = (1 << n) - 1;
	arr = vector<vector<int>>(n + 1);
	arr[0] = vector<int>(n + 1);
	for (int i = 1; i <= n; i++) {
		arr[i] = vector<int>(n + 1);
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	
	int dap = 2100000000;
	/*for (int i = 1; i <= n; i++) {
		int res = f(2, 1 << (i - 1)) + arr[1][i];
		dap = dap < res ? dap : res;
	}*/
	dap = f(1, 0);

	cout << dap;

	return 0;
}