[BOJ 24794] StopCard

백준 문제 링크

🔍 문제 분석

• 문제에서 최종 결과는 처음 뽑는 c개의 카드에 따라서 달라진다.
  1. 처음 c개에 가장 큰 수의 카드가 포함될 경우
  • 이 경우, 덱에있는 나머지 모든 카드를 뽑고 결과는 마지막으로 뽑은 카드가 된다. 마지막 카드는 가장 큰 수를 제외한 모든 카드가 동등한 확률로 나타난다. 따라서, 가장 큰 수를 제외한 평균을 계산한 뒤 등장 확률과 곱하여 기댓값을 계산한다. \(\frac{\binom{c-1}{n-1}}{\binom{c}{n}} \times \frac{\sum_{i=1}^{n} a_i - \max_{i=1}^{n} a_i}{n - 1}\)
    1. 처음 c개에 가장 큰 수의 카드가 포함되지 않는 경우
  • 이 경우, 처음 c개에 포함되어 있는 수 중 가장 큰 수보다 더 큰 수들 중 먼저 뽑힌 카드가 결과가 된다. 이 수들은 모두 동등한 확률로 나타나므로, 가능한 수들의 평균을 계산한 뒤 등장 확률과 곱하여 기댓값을 계산한다. 이 때, 처음 c개에 포함되어 있는 수 중 가장 큰 수가 될 수 있는 모든 수에 대하여 기댓값을 계산한 뒤 이를 더한다. \(E = \sum_{i=c}^{n-1} \left( \frac{\binom{i-1}{c-1}}{\binom{n}{c}} \times \frac{S_i}{n-i} \right)\) \(S_i = \sum_{j=i}^{n-1} a_j\)

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX_N = 64;

int n, c, a[MAX_N];
double cache[MAX_N + 1][MAX_N + 1];

double comb(int n, int m) {
    if (m == 0 || n == m) return 1;
    double& ret = cache[n][m];
    if (ret > 0) return ret;
    return ret = comb(n - 1, m) + comb(n - 1, m - 1);
}

int main() {
    fastio;

    fill(cache[0], cache[0] + (n + 1) * (n + 1), -1);

    cin >> n >> c;
    for (int i = 0; i < n; ++i) cin >> a[i];
    if (c == 0) {
        cout << accumulate(a, a + n, 0) / double(n);
        exit(0);
    }
    sort(a, a + n);
    double e = 0;
    int sum = 0;
    for (int i = c; i < n; ++i) sum += a[i];
    for (int i = c; i < n; ++i) {
        e += sum * comb(i - 1, c - 1) / double(n - i) ;
        sum -= a[i];
    }
    e += (accumulate(a, a + n, 0) - a[n - 1]) * comb(n - 1, c - 1) / double(n - 1);
    e /= comb(n, c);
    cout << fixed << setprecision(10) << e;
}

📝 코드 설명

🔧 트러블 슈팅

• c가 0인경우에 주의한다.
• 조합을 계산하는 부분에서 long long자료형을 사용했을 때 오버플로우가 발생했다. double로 변경해서 문제가 해결되었다.

📚 참고자료