[백준 1102] 발전소 풀이

문제 링크

분류

• 비트마스킹
• 다이나믹 프로그래밍

풀이

$DP[U] :=$ 집합 $U$ 에 속한 발전소들이 모두 켜지기 위한 최소 비용
DP 배열은 다음과 같이 구할 수 있습니다.

for a in U :
	for b in (U - {a}):
    	DP[U] = min(DP[U], DP[U - {a}] + weight[a][b]

U가 공집합 이거나 U에 속해 있는 발전소들이 이미 켜져있는 발전소들로만 구성되어 있다면 $DP[U] = 0$입니다.

코드

const int MAX_N = 16;
const int INF = 10000;
const ll MOD = 1e9 + 7;

int N;
int adj[MAX_N][MAX_N];
bool chk[MAX_N];
int DP[1 << MAX_N];
int P;
int ans = INF;

void preproc() {
  rep(i, MAX_N) rep(j, MAX_N) adj[i][j] = INF;
  for (int i = 0; i < (1 << MAX_N); ++i) {
    DP[i] = INF;
  }
}

void solve() {
  cin >> N;
  rep(i, N) rep(j, N) cin >> adj[i][j];
  string s;
  cin >> s;
  rep(i, N) {
    adj[i][i] = INF;
    if (s[i] == 'Y') chk[i] = true;
  }
  cin >> P;
  DP[0] = 0;
  for (int b = 1; b < (1 << N); ++b) {
    bool ok = true;
    for (int i = 0; i < N; ++i) {
      if (b & (1 << i)) {
        ok &= chk[i];
      }
    }
    if (ok) {
      DP[b] = 0;
    }
  }

  for (int b = 1; b < (1 << N); ++b) {
    for (int i = 0; i < N; ++i) {
      if (!(b & (1 << i))) continue;
      for (int j = 0; j < N; ++j) {
        if (i == j) continue;
        if (!(b & (1 << j))) continue;
        DP[b] = min(DP[b], DP[b ^ (1 << i)] + adj[j][i]);
      }
    }
  }

  for (int b = 0; b < (1 << N); ++b) {
    int tmp = b;
    int cnt = 0;
    while (tmp) {
      cnt += tmp % 2;
      tmp >>= 1;
    }
    if (cnt >= P) {
      ans = min(ans, DP[b]);
    }
  }

  cout << ((ans == INF) ? -1 : ans) << "\n";
}