007

백준 3056번: 007

아이디어

몇번 지미가 미션을 먼저 수행하는지는 신경쓸 필요가 없다. 각 미션의 할당 여부를 비트필드로 나타낸다. 지미 번호를 1씩 키우면서 넘겨준다. 모든 미션을 클리어했을 때 확률 변동이 없어야 하기 때문에 1을 반환한다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int prob[100][100];
double cache[1<<20];

double solve(int jimmy, int mission) {
    if (mission == (1<<N)-1) {
        return 1;
    }
    
    double& ret = cache[mission];
    if (ret != 0) return ret;
    
    ret = 0;
    for (int i = 0; i < N; i++) {
        if (mission&(1<<i)) continue;
        double tmp = solve(jimmy+1, mission|(1<<i))*prob[jimmy][i];
        ret = max(ret, tmp);
    }
    return ret;
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> prob[i][j];
        }
    }
    cout << fixed;
    cout.precision(6);
    cout << solve(0, 0)/pow(100, N-1);
    return 0;
}

여담

생각해보니까 PS하면서 처음으로 소수점을 다뤄봤다.

cout << fixed;
cout.precision(6);

라고 써주면 이 다음부터 소수점 6자리씩 나온다. 대박!