BOJ 3056 007

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

3056번: 007

 

비트마스킹을 통한 다이나믹 프로그래밍으로 해결할 수 있는 문제입니다. 원래 DP를 탑다운으로 주로 짜는데, 바텀업 연습을 해보고자 바텀업으로 구현했습니다.

 

1번 사촌부터 N번 사촌까지 차례대로 일을 배정하며 i번째 사촌까지 일을 배정했을 때 어떤 일들이 배정되었는지를 비트마스킹을 통해 표현해주었습니다. i번째 일이 배정되었다면 i번째 비트를 켜주는 식으로 구현하면 됩니다. 각 state에 대해 최댓값을 저장해주면 됩니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n;
double prob[20][20], memo[1 << 20];

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        cin >> prob[i][j];
        prob[i][j] /= 100;
      }
    }

    for (int j = 0; j < n; j++) memo[1 << j] = prob[0][j];
    for (int i = 1; i < n; i++) {
      for (int state = 1; state < (1 << n); state++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) if (state & (1 << j)) cnt++;
        if (cnt != i) continue;
        for (int j = 0; j < n; j++) {
          int newState = state | (1 << j);
          memo[newState] = max(memo[newState], memo[state] * prob[i][j]);
        }
      }
    }

    int finished = 0;
    for (int i = 0; i < n; i++) finished = finished | (1 << i);

    cout << fixed << setprecision(6);
    cout << memo[finished] * 100 << endl;
  }

  return 0;
}

 

플로우를 통해서도 풀 수 있다고 들었는데 플로우를 공부 안 해서 잘 모르겠습니다. 제한이 커져도 플로우로 풀 수 있다는 것 같습니다.