[ BOJ 백준 3056번 - 007 ] 해설 및 코드

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

 

목적

n명의 요원과 각 요원의 미션별 성공 확률이 주어질 때, 미션당 요원을 한명씩 배치하여 모든 미션을 수행할 때, 가장 높은 성공 확률을 구하자.

 

접근법

1. 완전 탐색 알고리즘을 구현해야 하며, 비트마스크를 이용해서 접근한다.

 

#include<iostream>
#include<cmath>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
int n,a[20][20];
double s[1<<20]={1};
 
int main(){
    cin>>n;f(i,0,n)f(j,0,n)cin>>a[i][j];
    cout.precision(6);
    cout<<fixed;
    
    f(i,0,1<<n){
        int cnt=__builtin_popcount(i);
        f(j,0,n)if((i&(1<<j))==0)s[i^(1<<j)]=max(s[i^(1<<j)],s[i]*a[j][cnt]/100);
    }
    cout<<s[(1<<n)-1]*100;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.