[백준/BOJ] 백준 1102번 : 발전소

https://www.acmicpc.net/problem/1102

1102번: 발전소

발전소가 켜진 상황을 비트로 나타내서 해당 상황에서 계산한 값을 다시 계산하지 않도록 다이나믹 프로그래밍을 이용했다. 

 

코드

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

int n;
int board[16][16];
string status;
int p;
int cache[1 << 16];

void Pre()
{
	for (int i = 0; i < (1 << 16); i++)
		cache[i] = -1;
}

//발전소가 켜진게 check인 상황에서 p개이상의 발전소를 켜는 비용 구하기
int Solve(int check, int cnt)
{
	//p개 이상 켜졌을때
	if (cnt >= p)
		return 0;

	int& ret = cache[check];

	if (ret != -1)
		return ret;

	ret = 987654321;

	for (int i = 0; i < n; i++)
	{
		//i번 발전소가 켜져 있을때
		if (((1 << i) & (check)) != 0)
		{
			//i번 발전소로 j번 발전소를 켜는것 확인
			for (int j = 0; j < n; j++)
			{
				//j번 발전소가 꺼져 있을때
				if (((1 << j) & (check)) == 0)
				{
					//i에서 j번 발전소를 키는 비용 고려
					check ^= (1 << j);
					ret = min(ret, Solve(check, cnt + 1) + board[i][j]);
					check ^= (1 << j);
				}
			}
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	cin >> status;
	cin >> p;

	int check = 0;
	int cnt = 0;

	for (int i = 0; i < status.size(); i++)
	{
		if (status[i] == 'Y')
		{
			check |= (1 << i);
			cnt++;
		}
	}

	//p가 0이 아닌데 처음에 켜진게 없을때
	if (p != 0 && cnt == 0)
		cout << -1;
	else
		cout << Solve(check, cnt);

	return 0;
}