백준 1102 발전소

dp 문제입니다. 16개 이하의 발전소가 있을 때 이발전소를 주어진 P개를 켜야 하는 문제인데 발전소의

켜짐 꺼짐 유무를 확인하기 위해 비트마스킹을 이용하여 해결을 하여야 합니다.

2^16만큼 잡아서 dp[70000] 정도로 잡아주면 되겠습니다.

 

이때 발전소를 키기 위해서는 켜진 발전소를 이용하여 꺼진 발전소를 키므로 각 함수에서

꺼진 발전소를 찾고 얘를 켤수 있는 발전소를 찾아서 재귀를 돌면 됩니다. 이때 cost가 0인것은 진짜로 0인 것이지 킬 수 없는게 아니라는 점(처음에 못키는줄 알았습니다.) 생각하면서 해결하면 됩니다. 외판원 순회문제와 유사한데 좀더 간단한(?) 문제 같습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

#define INF 987654321
using namespace std;

int cost[17][17];
int dp[100000]; //cur발전기 기준 visited 발전기들 켜짐
int P;
int N;

int sol(int visited, int cnt) {
	
	if (P == cnt) {
		return 0;
	}

	int& ret = dp[visited];
	if (ret != -1) return ret;
	ret = INF;

	for (int j = 0; j < N; j++) {
		if (!((1 << j) & visited)) { //꺼진 발전소 찾고 킬 발전소 아래에서
			for (int i = 0; i < N; i++) {
				if (i == j) continue;

				if (((1 << i) & visited)) { //발전소가 켜져있다면
					ret = min(ret, sol(visited | (1 << j), cnt + 1) + cost[i][j]);
				}

			}
		}
	}
	return ret;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> cost[i][j];

	int visited = 0;
	string str; cin >> str;
	cin >> P;

	for (int i = 0; i < str.size(); i++) {
		if (str[i] == 'Y') {
			P--;
			visited |= (1 << i);
		}
	}
	
	if (P <= 0) {
		cout << 0;
		return 0;
	}

	int ans = sol(visited, 0);
	if (ans == INF) cout << -1;
	else cout << ans;
	return 0;
}