[BOJ 3056, C++] 007

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

3056번: 007

 

풀이

N의 제한이 작으니 비트마스크를 이용해야 한다는 생각을 할 수 있습니다.

주의할 점은 계속 소수점이 나와야하기 때문에 double을 계속 사용하여 int형이 절대 나오지 않도록 주의해주면 됩니다. 정답률이 의외로 낮던데 아마 여기에서 많이 틀렸을 거라고 생각합니다.

문제에서 미션 성공률이 제일 높은 확률을 구하라고 했으므로 max를 이용하는 top-down 코드를 짜면 됩니다.

 

 

DP말고도 헝가리안 메소드나 MCMF를 사용하여 풀 수 있다고 하네요.

 

코드

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
 
const int N = 21;
double dp[1 << N], s[N][N];
int n;
 
double go(int x, int visit) {
    if (x == n) return 1.0;
 
    double& ret = dp[visit];
    if (ret != -1) return ret;
 
    ret = 0.0;
    for (int i = 0; i < n; i++) {
        if ((visit & (1 << i)) == 0) {
            ret = max(ret, go(x + 1, visit | (1 << i)) * s[x][i]);
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(11);
    for (int i = 0; i < (1 << N); i++) dp[i] = -1;
 
    cin >> n;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        cin >> s[i][j];
        s[i][j] *= 0.01;
    }
    
    cout << go(0, 0) * 100 << endl;
 
    return 0;
}