[백준] #1102 발전소 - (DP)

#include <iostream>
#include <cstring>
#define MAX 16+1
#define INF 987654321

using namespace std;

int N, P;
int arr[MAX][MAX];
//dp[x][y] => 현재 y상태에서 발전소 x번에서 시작할때의 최소비용
int dp[MAX][1 << MAX];
int state = 1 << MAX;
string str;

//주어지는 변수의 2진수형태에서 1의 개수를 파악
int count1(int n) {
	int cnt = 0;
	while(n) {
		cnt += n & 1;
		n >>= 1;
	}
	return cnt;
}
int func(int idx, int currState) {
	//currState의 1의 개수가 P-1개 이상 => P개의 발전소켜짐 => 0리턴
	//state의 초기값 맨 앞에 1이 기본적으로 추가가되므로
	if (count1(currState) -1 >= P)
		return 0;
	int &ref = dp[idx][currState];
	if (ref != -1)
		return ref;
	ref = INF;

	for (int i=0; i<N; ++i) {
		//꺼져있는 발전소를 킨후 상태 갱신
		if ( (currState & (1<<i)) == 0) {
			int nextState = (currState | (1<<i));
			for (int j=0; j<N; ++j) {
				//i번째 발전소를 키고, 그다음 켜져있는 발전소를 기준으로 함수 재귀호출
				if (nextState & (1<<j))
					ref = min(ref, func(j, nextState) + arr[idx][i]);
			}
		}
	}
	return ref;
}
int main() {
	cin >> N;
	for (int i=0; i<N; ++i) {
		for (int j=0; j<N; ++j) {
			cin >> arr[i][j];
		}
	}
	cin >> str;
	for (int i=0; i<str.length(); ++i) {
		if (str[i] == 'Y')
			state |= (1<<i);
	}
	cin >> P;
	//켜야할 목표 발전소개수가 0개인 경우
	if (P == 0) {
		cout << 0;
		return 0;
	}
	memset(dp, -1, sizeof(dp));
	////////////////////func////////////////////////
	//최종 최소비용값
	int result = INF;
	for (int i=0; i<N; ++i) {
		//켜져있는 발전소를 기준으로 dp함수 호출
		if (str[i] == 'Y') {
			result = min(result, func(i, state));
		}
	}
	//켜져있는 발전소가 없는경우 => 불가능
	if (result == INF)
		cout << -1;
	else
		cout << result;
}

문제

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

1102번: 발전소

목표

N개의 발전소와 발전소간 다른발전소를 키기위한 비용이 주어질때 P개의 발전소를 모두 키기위한 최소비용구하기

(단, 켜져있는 발전소에서만 꺼져있는발전소를 킬수 있다.)

 

풀이

dp사용, 비트를 사용하여 발전소의 상태정보를 저장한다.

dp[MAX][1<<MAX] => y상태에서 x에서 시작하여 다른 발전소P개 이상을 키기위한 최소비용

1. 초기상태에서 켜져있는 발전소를 상대로 한번씩 함수를 돌려본후 최소값을 구한다.

2. (초기상태에서 켜져있는 발전소를 하나 고른후) 꺼져있는 발전소를 찾는다.

3. 꺼져있는 발전소를 키고, 다시 켜져있는 발전소를 찾아 2,3번 과정을 반복하며 dp값을 만든다.

 

코드