백준 11009번 Drinks

문제 링크입니다: https://www.acmicpc.net/problem/11009

조합을 이용하여 확률을 계산하는 문제였습니다.

간단하게 문제를 해석하면 아래와 같습니다.

매주 주말에 drazil과 dreamoon은 공원에서 노는데 둘 중 한명이 모두의 음료수를 사야합니다. 그들은 다음과 같은 절차를 통해 누가 음료수를 살지 정하기로 약속했습니다.

1. n개의 빨간 구슬과 m개의 하얀 구슬을 가방에 넣습니다.

2. dreamoon과 drazil이 번갈아가면서 공을 꺼냅니다. 공을 꺼낼 때마다 가방에서 해당 구슬이 제거됩니다.

3. 빨간 구슬을 먼저 꺼내는 사람이 음료수를 사야합니다.

dreamoon이 drazil보다 연장자이기 때문에 drazil은 dreamoon이 먼저 뽑게 해줍니다. 어느날 dreamoon은 자기가 빨간 공을 뽑을 확률을 계산해지고 싶었습니다. 각각의 공을 꺼내는 확률이 동일할 때 dreamoon이 음료수를 살 확률을 계산하시오.

알고리즘은 아래와 같습니다.

1. 우선 빨간색 공을 꺼내는 모든 조합을 계산합니다.

2. 분모는 모든 경우여야 하므로 (n+m)Cn 입니다.

3. 한편, 분자는 계산하기 까다롭습니다.

i) dreamoon이 먼저 꺼내는데 바로 빨간 공을 꺼내는 경우

ii) dreamoon이 먼저 꺼내는데 하얀색 공을 꺼내고 drazil 또한 하얀색 공을 꺼내고 dreamoon이 빨간색 공을 꺼내는 경우

iii) dreamoon이 먼저 꺼내는데 하얀색 공을 꺼내고 drazil 또한 하얀색 공을 꺼내고 dreamoon 또한 하얀색 공을 꺼내고 drazil 또한 하얀색 공을 꺼내고 마지막에 dreamoon이 빨간색 공을 꺼내는 경우

...

iV) 가능한 모든 경우를 더해줍니다

4. 3번에서 구한 값 / 2번에서 구한 값을 출력해줘야하는데 기약분수 형태로 출력해줘야합니다.

-> 따라서, 최대공약수로 분자와 분모를 나누고 출력해줍니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 60 + 1;

 

long long cache[MAX][MAX];

 

//유클리드 호제법

long long GCD(long long a, long long b)

{

        return b ? GCD(b, a%b) : a;

}

 

void preCalculate(void)

{

        //Combination 미리 계산

        for (int i = 0; i < MAX; i++)

        {

                 cache[i][0] = 1;

                 for (int j = 1; j <= i; j++)

                         cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j];

        }

}

 

int main()

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int test_case;

        cin >> test_case;

 

        preCalculate();

        for (int t = 0; t < test_case; t++)

        {

                 int red, white;

                 cin >> red >> white;

 

                 //red를 뽑는 모든 경우의 수

                 long long denominator = cache[red + white][red];

                 long long numerator = 0;

                 //drazil은 white를 뽑고 dreamoon은 red를 뽑을 경우 모두 계산

                 for (int i = red + white - 1; i >= 0; i -= 2)

                         numerator += cache[i][red - 1];

 

                 cout << numerator / GCD(numerator, denominator) << "/" << denominator / GCD(numerator, denominator) << "\n";

        }

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~