백준 1102: 발전소

문제 요약

은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다.

발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다.

적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오.

문제 분류

• 다이나믹 프로그래밍
• 비트마스킹
• 비트필드를 이용한 다이나믹 프로그래밍

문제 풀이

다른것보다 우선 발전소의 on/off를 비트로 표현한다. YNN은 즉 100(2)가 되는 것이다. 그렇게 현재 상태와 발전소가 켜진 개수를 매개변수로 보내서 DP로 풀면 된다.

DP로 푸는 이유는 다음과 같다. 우선 그리디로는 절대 불가능하고, 결국 모든 경우의 수를 다 해보아야 하는데, 중복되는 경우가 많다. 가령 YNYNN에서 YYYNN으로 만들 수 있고 YYNNN에서도 YYYNN으로 만들 수 있는데, YYYNN에서의 값을 동일할 것이기 때문이다. 중복되는 재귀호출이 많으므로 DP로 풀면 되는 것이다.

DP[state]는 현재 상태(state)에 대한 최소 비용을 의미한다. 예제 입력 1을 예로 들자면, YNN의 100(2) 즉, DP[4]는 100(2)에서 111(2)이 되기까지의 최소 비용을 의미한다. YYN의 110(2), DP[6]은 111(2)이 되기까지의 최소 비용이므로, 3번째가 발전기가 켜지는 최소의 비용을 넣으면 된다. 1에서 영향을 받든, 2에서 영향을 받든 상관없다.

다시 말해서 DP탐색을 할 때에는 다음에 켤 발전기를 정해놓고(비트가 0인부분을 탐색), 그 발전기가 켜지기 위한 최소 비용을 다음 상태에 더하면 된다. 이 다음 상태에 대한 최소 비용은 재귀호출로 구하면 된다.

불가능할 때에는 -1을 출력해주는 것을 잊지 말자. 또한, 켜진 발전기의 개수가 P보다 클 때가 base case이므로 그때 0을 반환하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <memory.h>
const int INF = 2000000000;
using namespace std;

int dp[1 << 16], ary[16][16];
int n, des = 0;

int sol(int state, int cnt) {
	if (cnt >= des) return 0;
	if (dp[state] != -1) return dp[state];
	int& res = dp[state], stemp;

	res = INF;
	for (int i = 0; i < n; i++) {
		if (!(state & (1 << i))) {
			stemp = INF;
			for (int j = 0; j < n; j++)
				if (state & (1 << j)) stemp = min(stemp, ary[n - j - 1][n - i - 1]);
			if (stemp == INF) return -1;
			res = min(res, sol(state | (1 << i), cnt + 1) + stemp);
		}
	}

	return res;

}

int main()
{
	int state = 0, oncnt = 0;
	char in = NULL;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			scanf("%d", &ary[i][j]);
	}
	getchar();
	for (int i = n - 1; i >= 0; i--) {
		scanf("%c", &in);
		if (in == 'Y') {
			state |= 1 << i;
			oncnt++;
		}
	}
	getchar();
	scanf("%d", &des);
	memset(dp, -1, sizeof(dp));
	cout << sol(state, oncnt);
	return 0;
}