[백준 1311] 할 일 정하기 1

아이디어

• 비트마스킹을 사용할 줄 안다
• 비트마스킹을 이용한 dp를 활용할 줄 안다.

접근방식

1. dp라는 배열을 만들고, dp[비트]로 활용하되, 비트는 '일을 선택한 곳을 1로 켠 비트'로 저장해준다
2. 우선 0번 사람의 0번~n-1번까지의 일을 했다고 초기화 해주고, 그 비트를 vector에 저장해준다
3. 1번~n-1번까지 사람을 한번씩 확인하면서, 이전 사람까지의 비트 기록을 참조, dp[다음비트]가 더 작을 경우 갱신 후 vector에 저장, 만약 아니라면 continue로 넘겨준다
   -> 왜?? ex) 1,2,3번이 a,b,c번 일을 한다고 하면, 1-a | 2-b 나 2-a | 1-b를 해도 어짜피 c는 3번 일 밖에 할 수 가 없다. 즉, 1,2번을 같은 번호의 사람들이 일하게 된다면, 그중에 가장 최솟값을 가져오면 된다.

#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int work[20][20];
int dp[3000000];


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

	int n; cin >> n;

	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			int num; cin >> num;
			work[row][col] = num;
		}
	}

	vector<int> v[20];

	for (int i = 0; i < n; i++) {
		v[0].push_back((1 << i));
		dp[(1 << i)] = work[0][i];
	}

	for (int now = 1; now < n; now++) {

		vector<int> bit_list = v[now - 1];

		for (int i = 0; i < bit_list.size(); i++) {

			int now_bit = bit_list[i];

			for (int col = 0; col < n; col++) {
				int work_pay = work[now][col];
				int next_bit = now_bit | (1 << col);

				if (now_bit == next_bit) { //같은 bit면 중복된 일을 한다는뜻
					continue;
				}

				else if (dp[next_bit] > dp[now_bit] + work_pay || dp[next_bit] == 0) {
					dp[next_bit] = dp[now_bit] + work_pay;
					v[now].push_back(next_bit);
				}
			}
		}
			
	}

	cout << dp[(1 << n) - 1] << endl;

	return 0;
}

평가

비트마스킹과 dp를 동시에 알아야하는 문제.
비트마스킹은 알고 있었고, dp도 사용하는 것을 눈치챘으나,
저는 처음에 dfs로 돌릴때 계속 시간초과가 났었습니다.
아무래도 dfs는 모든 일을 할때까지 깊게 들어가므로, dp로 가지치기를 하고 싶어도, 맨 마지막에 가지치기를 하게되어 시간초과가 난게 아닌가 싶습니다.