[BOJ]1102 : 발전소(c++)

[문제] : https://www.acmicpc.net/problem/1102

[풀이]

비트마스킹 + DP 문제이다. 현재 발전소의 상태를 비트마스킹을 통해 나타내야 한다. 반복문을 사용해 켜져있지 않은 발전소를 탐색하여 어떤 발전소를 켜야 비용이 최소가 되는지를 찾았다. dp함수에서 x를 현재 켜야하는 발전소, cur이 현재 발전소 상태, ht가 켜야하는 발전소의 수를 나타내게 하였고 ht가 0보다 작거나 같을때, x가 켜져있을때는 0을 리턴, 만약 발전소를 킬 수 없는 상황일때는 INF 값이 리턴되게 하였다.

[코드]

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#define INF 0x3f3f3f3f

using namespace std;

int N;
int cost[17][17];
string yon;
int al;
int cache[17][1 << 17];

int dp(int x, int cur, int ht)
{
	if (ht <= 0) return 0;
	if (yon[x] == 'Y') return 0;
	int& ret = cache[x][cur];
	if (ret != INF) return ret;

	int va = 37;
	for (int i = 0; i < N; ++i)
	{
		int t = (1 << i);
		if (i == x) continue;
		if (t & cur)
		{
			va = min(va, cost[i][x]);
		}
	}
	if (va == 37) return INF;
	cur |= (1 << x);
	for (int i = 0; i < N; ++i)
	{
		if(!((1 << i) & cur))
			ret = min(ret, dp(i, cur, ht - 1) + va);
	}

	if (ret == INF) return va;
	return ret;

}

int main(void)
{
	memset(cache, INF, sizeof cache);
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> cost[i][j];

		}
	}

	cin >> yon;
	int cnt = 0;
	int on = 0;
	for (int i = 0; i < yon.size(); ++i)
	{
		if (yon[i] == 'Y') {
			on |= (1 << i);
			cnt++;
		}
	}
	cin >> al;

	int ht = al - cnt;

	if (ht <= 0)
	{
		cout << 0 << endl;
	}
	else
	{
		int res = INF;
		for (int i = 0; i < N; ++i)
		{
			if (!((1 << i) & on))
				res = min(res, dp(i, on, ht));
		}

		if (res == INF) res = -1;
		cout << res << endl;

	}

}

[느낀점]

비트마스킹을 이용한 문제는 재밌으면서도 어렵다.. 처음에는 0번 발전소부터 순서대로 키거나 끄는 경우를 생각했는데 이렇게 되면 기저조건을 설정하기 까다로워져서 반복문을 통해 현재 어떤 발전소를 키는게 이득인지 찾는 코드를 작성하게 되었다.

지적 환영합니다