https://www.acmicpc.net/problem/3056
목적
n명의 요원과 각 요원의 미션별 성공 확률이 주어질 때, 미션당 요원을 한명씩 배치하여 모든 미션을 수행할 때, 가장 높은 성공 확률을 구하자.
접근법
1. 완전 탐색 알고리즘을 구현해야 하며, 비트마스크를 이용해서 접근한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#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;
}
|
문제 설명과 코드에 대한 피드백은 언제나 환영합니다.
다양한 의견 댓글로 남겨주세요.
'Problem Solving > BOJ 백준' 카테고리의 다른 글
[ BOJ 백준 16434번 - 드래곤 앤 던전 ] 해설 및 코드 (0) | 2019.12.16 |
---|---|
[ BOJ 백준 3649번 - 로봇 프로젝트 ] 해설 및 코드 (0) | 2019.12.16 |
[ BOJ 백준 3980번 - 선발 명단 ] 해설 및 코드 (0) | 2019.12.16 |
[ BOJ 백준 3090번 - 차이를 최소로 ] 해설 및 코드 (0) | 2019.12.14 |
[ BOJ 백준 15732번 - 도토리 숨기기 ] 해설 및 코드 (0) | 2019.12.13 |