백준 7638 (C++) Betting Sets

최초 업로드: 2025-09-20 05:46:46

최근 수정 시간: 2025-09-20 05:46:46

게시자: rlatjwls3333

카테고리: 백준

# [Silver II] Betting Sets

[문제 링크](https://www.acmicpc.net/problem/7638)

## 문제 설명

Your local casino (which here in California is a fair distance away) has decided to try out a new betting game. The player is given a table on a card with N rows and M columns. Each entry ij of the table corresponds to a coin flip with a probability pij of coming up heads. All the coin flips are independent of each other. The player must choose N sets of M entries, with each set having exactly one entry from each column, and each entry being used exactly once. For each chosen set where all M coins come up heads, the player wins 1 dollar. The casino is feeling uncharacteristically generous, and so as part of the promotion of this new game, they have been handing out one card to each patron. Since you have nothing to lose, you’re going to give this game a shot. How can you maximize your expected winnings from this card?

## 입력

The input consists of multiple test cases. Each test case begins with a line with two integers N and M, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10, separated by a space. This is followed by N lines with M space-separated numbers each, denoting the entries pij of the table. Input is followed by a single line with N = M = 0, which should not be processed.

## 출력

For each test case, print out a single line with the maximum expected winnings from the given table, accurate to 4 decimal places.

## 풀이
문제에서 N * M 테이블이 주어집니다. 총 N번 게임을 반복해야 하고, 세로줄에선 아무 동전이나 선택해서 사용해도 되고 재사용 불가능하니, 확률을 최대화하려면 i번째로 큰 확률끼리 곱해주면 됩니다. 이를 정렬으로 구현하였습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long double ld;

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 while(true) {
 int n, m; cin >> n >> m;
 if(!n) break;
 vector<vector<ld>> percent(m, vector<ld>(n));
 for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> percent[j][i];
 for(int i=0;i<m;i++) sort(percent[i].begin(), percent[i].end(), greater<ld>());

ld total=0;
 for(int i=0;i<n;i++) {
 ld cur=1;
 for(int j=0;j<m;j++) cur *= percent[j][i];
 total += cur;
 }
 cout << fixed << setprecision(4) << total << '\n';
 }
}
```