백준 1102번: 발전소 비트마스킹 DP C++

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

1102번: 발전소

 

 

 

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, arr[16][16], p, dp[1<<16];
string str;
int state = 0;
int cnt = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(dp, 0x3f, sizeof(dp));

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	cin >> str;
	cin >> p;

	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'Y') {
			state |= (1 << i);
			dp[1 << i] = 0;
			cnt++;
		}
	}


	if (cnt >= p) {
		cout << 0 << '\n';
		return 0;
	}
	else if (cnt == 0 && p != 0) {
		cout << -1 << '\n';
		return 0;
	}
	else if (cnt == 0 && p == 0)
	{
		cout << 0 << '\n';
		return 0;
	}

	dp[state] = 0;
	dp[0] = 0;

	for (int mask = 0; mask < (1 << n); mask++) {
		for (int i = 0; i < n; i++) {
			if (mask & (1 << i)) {
			// 현재 i 발전소 켜져있음
				for (int j = 0; j < n; j++) {
					if (i == j) continue;
					int pre = mask ^ (1 << j);
					if (dp[pre] >= INF) continue;
					dp[mask] = min(dp[mask], arr[i][j] + dp[pre]);
				}
			}
		}
	}

	int res = INF;
	for (int i = 0; i < (1<<n); i++) {
		int cnt = 0;
		for (int j = 0; j < n; j++) {
			cnt += ((i >> j) & 1);
		}

		if (cnt >= p) {
			res = min(res, dp[i]);
		}
	}

	cout << res << '\n';

	return 0;
}