[BOJ] 백준 3980. 선발 명단 (Gold IV)

*주의*

정해와 다르게 해결하였으며, 정해 풀이는 올리지 않습니다.

 

스터디그룹 연습에서 B번으로 나온 문제.

문제는 아래와 같다.

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

3980번: 선발 명단

---

의식의 흐름 및 해설

문제 이해가 조금 힘든데, 쉽게 풀이하자면 모든 포지션에 한 명 이상의 선수가 위치해야 된다.

모든 포지션에 선수가 위치해야 되므로 TSP와 똑같다.

그러므로 이 문제와 거의 유사하다.

https://kth990303.tistory.com/61

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

주의할 점은 Sij = 0일 경우 불가능하다는 점을 코드에 추가 구현해주어야 한다는 점.

참고로 N이 16~20 정도가 아니고 10이기 때문에 O(N!) 백트래킹 풀이도 충분히 가능하다.

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 13;
const int INF = 0x3f3f3f3f;
int t,N=11, a[MAX][MAX], d[MAX][1 << 13];
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(!a[cur][i])continue;
		if (!(flag & (1 << i)))
			ret = max(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 >> t;
	while(t--){
		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";
	}
}

---

풀고나니 티어가 낮아 당황했는데,

N이 더 작았다.

본의아니게 오버킬해버린 문제ㅋㅋ