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

문제 출처: https://www.acmicpc.net/problem/1102

1102번: 발전소

비트필드를 이용하여 고장여부를 확인하고 모든 고장 나지 않은 발전소에서 모든 고장난 발전소를 고쳐보며(2중 for) 최소값을 얻어낸다.

 

비트필드를 이용하는 문제인 외판원 순회에서는 dp[idx][bitfield]로 구성 되었다. 만약 비트필드로만 구성된 dp[bitfield]였다면 bitfield가 15(1111)인 경우 1-> 2 -> 3 -> 4 경로와 1 - > 3 - > 2 - > 4  경로에 대한 값이 똑같은 인덱스에 쓰여지는 문제가 있었기 때문이다.

 

발전소 문제에서도 이런 문제가 있을꺼라고 생각하고 dp[idx][bitfield]로 구성하려고 했으나  1 - > 2 수리 후 1 - > 3수리를 하는 경우나 1 - > 3 수리 후 1 - > 2 수리를 하는 경우나 똑같기 때문에 bitfelid로만 구성되어도 상관이 없다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;

int N, P;
int arr[16][16];

int dp[1 << 16];
const int INF = 123456789;
int minV = INF;

int repair(int visited, int count) {
	if (count == P) return 0;
	if (dp[visited] != -1)return dp[visited];

	vector<int> notBreak;
	vector<int> Break;
	for (int i = 0; i < N; i++) {
		if ((visited >> i) & 1)notBreak.push_back(i);
		else Break.push_back(i);
	}

	int val = INF;
	for (int i = 0; i < notBreak.size(); i++) {
		for (int j = 0; j < Break.size(); j++) {
			
			int nB = notBreak[i];
			int B = Break[j];
			val = min(val , repair(visited | (1 << B) , count+1) + arr[nB][B]);
		}
	}

	return dp[visited] = val;
}



int main(void)
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> N;
	for (int i = 0; i < N; i++)	
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];
	
	string temp; cin >> temp;
	int visited = 0, count = 0;

	for (int i = 0; i < N; i++) {
		if (temp[i] == 'Y') { 
			visited = visited | (1 << i);
			count++;
		}
	}
	cin >> P;



	if (count >= P) {
		cout << "0";
		return 0;
	}
	else if (count == 0) {
		cout << "-1";
		return 0;
	}
	cout << repair(visited, count);


	
}