BOJ1102 발전소(C++)

---

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

태그 : dp, 비트마스킹, 비트필드dp

---

사고 과정

문제가 굉장히 직관적이라 바로 dp인 것을 알 수 있을 정도이다.

n개의 발전소가 켜지기 위해선 n - 1개가 켜진 상태에서, 어떤 발전소에서 한 개의 발전소를 켜면 되니까..

dp[i][j] = i개 사용했을 때 j상태를 만들 수 있는 최소 비용 으로 정의하였다.

처음엔 갯수에 꽂혀서, 최대 65536까지 수 각각의 비트 갯수를 저장해놓고,

비트 갯수가 하나 적은 쪽에서 전이로 가져오도록 코드를 짰다.

그런데 잘 생각해보면, 굳이 개수를 사용하지 않아도

0에서 전이를 시작하면 무조건 갯수가 큰 쪽으로 전이가 된다.

특정 비트 상태는 무조건 그보다 작은 수에서 고려가 되어있을 거니까...

그래서 dp[bitmask] 1차원 dp배열로도 풀이가 된다.

---

코드 : 1차원 dp

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

#define INF 1000000007

int n, ans = INF, p;
int arr[16][16];
string s;
int dp[1 << 16];

void solve() {

	for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
		for (int i = 0; i < n; ++i) {
			if ((bitmask >> i) & 1) {
				for (int j = 0; j < n; ++j) {
					if (i != j) {
						int next = bitmask | (1 << j);
						dp[next] = min(dp[next], dp[bitmask] + arr[i][j]);
					}
				}
			}
		}
	}

	for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			if ((bitmask >> i) & 1) {
				++cnt;
			}
		}
		if (cnt >= p) {
			ans = min(ans, dp[bitmask]);
		}
	}
}

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

	cin >> n;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < (1 << n); ++i) {
		dp[i] = INF;
	}


	cin >> s;
	int flag = 0;
	int bitmask = 0;
	int cnt = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] == 'Y') {
			++cnt;
			flag = 1;
			bitmask += (1 << i);
		}
	}
	dp[bitmask] = 0;
	cin >> p;

	if (cnt < p) {
		if (flag) {
			solve();
		}
		else {
			ans = -1;
		}
	}
	else {
		ans = 0;
	}

	cout << ans;
}

---

코드 : 2차원 dp

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

#define INF 1000000007

int n, ans = INF, p;
int arr[16][16];
string s;
int dp[17][1 << 16];
vector<int> v[17];

void solve() {
	for (int j = 0; j < (1 << n); ++j) {
		int cnt = 0;
		for (int k = 0; k < n; ++k) {
			if ((j >> k) & 1) {
				++cnt;
			}
		}
		v[cnt].push_back(j);
	}

	for (int i = 2; i <= n; ++i) {
		for (int j = 0; j < v[i - 1].size(); ++j) {
			int prv = v[i - 1][j];
			for (int k = 0; k < n; ++k) {
				if ((prv >> k) & 1) {
					for (int l = 0; l < n; ++l) {
						if (k != l  && ((prv >> l) & 1) == 0) {
							int next = prv + (1 << l);
							dp[i][next] = min(dp[i][next], dp[i - 1][prv] + arr[k][l]);
							if (i >= p) {
								ans = min(ans, dp[i][next]);
							}
						}
					}
				}
			}
		}
	}
}

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

	cin >> n;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j < (1 << n); ++j) {
			dp[i][j] = INF;
		}
	}

	cin >> s;
	int flag = 0;
	int cnt = 0;
    int bitmask = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] == 'Y') {
			flag = 1;
			bitmask += (1 << i);
			++cnt;
		}
	}
    dp[cnt][bitmask] = 0;
	cin >> p;

	if (cnt < p) {
		if (flag) {
			solve();
		}
		else {
			ans = -1;
		}
	}
	else {
		ans = 0;
	}

	cout << ans;
}

---

후기

1차원 dp가 가능하다는 것을 알게 된 것이 고무적이다.

2차원dp로는 시간이 애매할 수도 있다고 생각했는데, 44ms로 의외로 괜찮게 나왔다.