백준 3056번: 007
8756 단어 bitmaskingpsDPcppDP
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자리씩 나온다. 대박!
Author And Source
이 문제에 관하여(백준 3056번: 007), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-3056번-007저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)