백준 1102 : 발전소

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

1102번: 발전소

 

비트마스킹 + DP 문제다.

 

비트마스킹을 하는 데, 켜져있는 비트의 수와 현재 숫자를 동시에 확인하기 좋은 STL bitset을 사용하였다.

 

켜져있는 발전기는 1, 꺼져있다면 0으로 처리해준 후 백트래킹으로 고치는 순서 순열을 만들어주었고, 탑다운 방식으로 dp배열에 메모이제이션 해주어 동일한 연산이 반복되지 않도록 처리했다.

 

#include <iostream>
#include <string>
#include <bitset>

#define min(a,b) a<b?a:b
using namespace std;

int n, p;
int adj[17][17];
bitset<16> bs;
int dp[(1 << 16) - 1];

int dfs() {
	if (bs.count() >= p) return 0;

	int cur_bit = bs.to_ulong();
	if (dp[cur_bit] != -1) return dp[cur_bit];

	int min_cost, cur_cost;
	dp[cur_bit] = 1e9;
	for (int i = 1; i <= n; i++) {
		if (bs[i - 1]) continue;

		cur_cost = 50;
		for (int j = 1; j <= n; j++) {
			if (!bs[j - 1]) continue;
			cur_cost = min(cur_cost, adj[j][i]);
		}

		bs[i - 1] = 1;
		min_cost = dfs();
		dp[cur_bit] = min(dp[cur_bit], cur_cost + min_cost);
		bs[i - 1] = 0;
	}

	return dp[cur_bit];
}

void solution() {
	int works = 0;
	string s;

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> adj[i][j];
		}
	}
	
	cin >> s >> p;
	for (int i = 1; i <= n; i++) if (s[i - 1] == 'Y') bs[i - 1] = 1;
	for (int i = 0; i < (1 << n) - 1; i++) dp[i] = -1;

	// 켜진 발전기가 하나도 없을 경우, 예외처리
	if (bs.count() == 0 && p) {
		cout << -1; return;
	}

	dp[bs.to_ulong()] = -1;
	cout << dfs();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2280 kb

시간: 16 ms