[C++] 백준 1102번: 발전소

문제 링크

1102번: 발전소

문제 요약

발전기들로 이루어진 그래프가 주어진다. 이 그래프에서 발전기들은 켜져 있거나 꺼져 있다. 꺼져 있는 발전기는, 인접한 켜져 있는 발전기로 켤 수 있다. 발전기를 켤 때는 비용이 든다. 이 그래프에서 최소한 P개의 발전기가 켜져 있도록 하기 위한 최소 비용을 구해야 한다.

접근 방법

비트마스킹 DP 문제였습니다. 켜져 있는 발전기의 수를 센 다음에, 이 수가 P와 같아질 때까지 재귀호출을 합니다. 각 재귀호출 단계에서 켜져 있는 발전기 i, 꺼져 있는 발전기 j 사이의 비용을 더해주면서 현재 상태에서 만들 수 있는 최솟값을 갱신해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, p, cost[16][16], dp[1 << 16];

int func(int cnt, int bit)
{
	if (cnt == p)
		return 0;

	if (dp[bit] == 1e9)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if ((bit & 1 << i) && !(bit & 1 << j))
					dp[bit] = min(dp[bit], func(cnt + 1, bit | (1 << j)) + cost[i][j]);

	return dp[bit];
}

int main(void)
{
	cin >> n;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> cost[i][j];

	int cnt = 0, bit = 0;
	for (int i = 0; i < n; i++)
	{
		char c;
		cin >> c;

		if (c == 'Y')
			bit |= (1 << i), cnt++;
	}

	cin >> p;

	if (p && !cnt)
		cout << -1;
	else if (cnt >= p)
		cout << 0;
	else
	{
		fill_n(dp, 1 << 16, 1e9);
		cout << func(cnt, bit);
	}

	return 0;
}