[PS] 발전소 / C++ (백준 1102번)

발전소 (백준 1102번)

 

비트필드를 이용한 dp 문제로 n이 16 이하의 자연수이기 때문에 $O(2^{n}*n^{2})$으로 해도 최대 16,777,216이 나오기 때문에, 시간초과가 나오지 않는다.

 

풀이 과정

 dp 점화식을 dp[i][j] = 'i개의 발전소가 작동할 때, 발전소 상태가 j인 경우 드는 최소 비용' 으로 잡는다. 이때, j에 들어가는 값은 비트필드로 각 비트는 n(n-1)(n-2)...54321와 같이 내림차순으로 n~1번 발전소의 고장 여부를 나타낸다.

(n이 5라고 가정했을 때, j가 10110이면 5, 3, 2번 발전소가 켜져있다는 뜻)

 

 초기 dp 배열은 -1로 초기화하고, 작동중인 발전소들을 나타내는 값(: bit)을 구해서 dp[작동중인 발전소 수(: cnt)][bit]를 0으로 초기화해준다. 이후 다음 순서를 반복하며 dp[cnt+1 ~ p] 배열을 채워주면 된다.

1. j 상태에서 작동중인 발전소 k를 찾고, dp[i-1][ j^(1<<(k-1)) (j 상태에서 k를 제외한 상태: before)]가 -1이 아닌지 확인하여 i - 1개의 발전소가 작동하며, k가 작동하지 않던 상태(before)가 있었는지 확인한다.
2. before 상태에서 작동하는 발전소들을 사용하여 발전소 k를 켜는 값들중 최솟값(:cost)을 찾는다.
3. 조건에 맞다면 dp[i][j] 값을 갱신한다.

 이후, dp[p][0~(1<<n)] 중에 작동하는 발전소가 p개인 상태의 비용중 최솟값을  출력해주면 된다. 

#include<iostream>
#include<algorithm>
using namespace std;

int d[21][21], dp[21][100'001];
char ch[21];

int main()
{
	int n, p, cnt = 0, bit = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &d[i][j]);
		}
	}

	for(int i=0; i<=n; i++){
		for (int j = 0; j < (1 << n); j++) {
			dp[i][j] = -1;
		}
	}

	scanf(" %s %d", ch, &p);
	for (int i = 1; i <= n; i++) {
		if (ch[i - 1] == 'Y') {
			cnt++;
			bit = bit | (1 << (i - 1));
		}
	}

	if (cnt >= p) {
		printf("0\n");
		return 0;
	}

	if (bit != 0)dp[cnt][bit] = 0;
	for (int i = cnt + 1; i <= p; i++) {
		for (int j = 1; j < (1 << n); j++) {
			for (int k = 1; k <= n; k++) {
				int before = j ^ (1 << (k - 1));
				if (j & (1 << (k - 1)) && dp[i - 1][before] != -1) {
					int cost = 2e9;
					for (int l = 1; l <= n; l++) {
						if (before & (1 << (l - 1)))cost = min(cost, d[l][k]);
					}
					if (cost == 2e9)continue;
					if (dp[i][j] == -1 || dp[i][j] > dp[i - 1][before] + cost)dp[i][j] = dp[i - 1][before] + cost;
				}
			}
		}
	}

	int dap = 2e9;
	for (int i = 0; i < (1 << n); i++) {
		cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (i | (1 << (j - 1)))cnt++;
		}
		if (dp[p][i] != -1 && cnt >= p)dap = min(dap, dp[p][i]);
	}
	printf("%d\n", dap == 2e9 ? -1 : dap);

	return 0;
}