[백준/BOJ] 14853번 : 동전 던지기 (조합론, Diamond II)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14853번 : '동전 던지기' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Diamond II에 해당하며, 문제를 풀이하기 위해 조합론에 대한 배경 지식이 필요합니다.

 

 

14853번 : 동전 던지기

14853번: 동전 던지기

 

[0, 1]에서 균등한 확률을 가지는 p와 q가 각각 동전 1과 동전 2를 던졌을 때 앞면이 나오는 확률이라고 했을 때, 동전 1을 n1번 던졌더니 앞면이 m1번 나오고 동전 2를 n2번 던졌을 때 앞면이 m2번 나왔다면 p < q일 확률은 얼마인지를 구하는 문제입니다.

 

 

 

조합론 문제에서 가장 중요한 것은 동일한 답이 얻어지는 상황으로 치환시켜서 푸는 아이디어입니다.

앞면이 나올 확률이 p인 동전의 앞면이 나오는 상황은, 구간 [0, 1]에서 임의의 한 점을 찍어 p의 왼쪽의 점이 오는 경우로 치환시켜서 생각할 수 있습니다.

예를 들어 동전을 5개 던진 상황은 위와 같이 [0, 1] 구간의 임의의 위치에 무작위적으로 점을 5개 잡은 상황으로 생각할 수 있습니다.

 

 

 

이 문제에서는 p와 q 역시 무작위로 결정되기 때문에, 이 p와 q 역시 선택되는 하나의 점으로 생각할 수 있습니다.

따라서 동전 1을 n1번, 동전 2를 n2번 던진 상황은 [0, 1] 구간의 선분 위에 n1+n2+2개의 점을 선택하는 것과 같습니다.

결론적으로 동전 1을 n1번, 동전 2를 n2번 던진 상황은 [0, 1] 위의 무작위의 n1+n2+2개의 점 중 동전 1에 해당하는 사건을 선택하는 경우의 수가 모든 경우의 수에 해당하므로, 분모는 n1+n2+2 C n1+1으로 생각할 수 있습니다.

 

이해를 돕기 위해 수직선에 빨간 점(동전 1)과 파란 점(동전 2)로 나타내어 보겠습니다.

 

 

 

동전 1의 사건들을 기준으로 점들을 선택하면 나머지 점들은 동전 2에 해당하므로 동전 1을 기준으로 점들을 선택해보겠습니다.

점 p를 기준으로 그 왼쪽에 있는 점들을 k개라고 하면, 동전 1의 앞면이 m1번 나와야 문제 상황의 조건이 되므로 k개 중 m1개를 선택해주어야 합니다. (k C m1)

또한 점 p를 기준으로 그 오른쪽에 있는 점들은 n1+n2+2-k-1 = n1+n2+1-k개이고, 이들 중 동전 1의 뒷면이 나온 횟수에 해당하는 n1-m1개를 선택해주어야 합니다. (n1+n2+1-k C n1-m1)

 

이제 아까 가정한 k는 최소 m1개, 최대 m1+m2개일 수 있으므로 이 모든 경우의 수를 고려해주기 위해 k에 대한 시그마 합으로 분자를 나타낼 수 있습니다.

따라서 최종적인 확률 식은 위와 같이 나타낼 수 있게 됩니다.

 

 

 

수학 문제였다면 여기서 끝났겠지만, 아직 수행해야 할 절차가 남아있습니다.

프로그래밍 문제이므로, 주어진 자료형과 시간 제한 안에 프로그램이 값을 계산할 수 있도록 식을 조작해줄 필요가 있습니다.

 

가장 간단한 방법은, k = m1에 대한 식을 먼저 계산하고, k = m1+1일 때 바뀌는 부분들을 적절히 곱하고 나눠서 더해주고, k = m1+2일 때 다시 곱하고 나눠서 더해주고, ...하는 방식을 반복하는 것입니다.

따라서 우선 k = m1일 때 식을 정리해보면 위와 같이 나타낼 수 있습니다.

 

 

 

그 다음 k = m1+1일 때 식을 정리해서 k = m일 때와 달라진 부분들을 나타내면 위와 같이 됩니다.

사실 k = m1+1까지만 해보고 부호를 결정하기는 불가능하므로 최소한 k = m1+2까지는 해보셔야 합니다.

저는 풀이를 미리 해봤기 때문에 k = m1+1에서 부호를 결정하여 빨간색으로 나타내었습니다.

 

 

 

따라서 빨간색 식을 먼저 계산해서 temp와 ans라는 변수에 저장해두고, temp에 우측 식을 계속 곱하고 ans에 더하는 방식으로 계산하면 시간 초과를 피해 빠른 시간 안에 답을 계산할 수 있습니다.

 

이 때 주의할 점은 오차를 최대한 피하기 위해 double 자료형을 이용하여 계산하여야 하며, overflow를 방지하기 위해 비슷한 수끼리 분자 및 분모를 묶어서 계산해야 한다는 것입니다.

 

이제 이 풀이를 코드로 구현해보도록 하겠습니다.

 

 

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        double n1, m1, n2, m2; cin >> n1 >> m1 >> n2 >> m2;

        double temp = 1;
        for(int i=0; i<=m1; i++)
            temp = temp * (n1 + 1 - i) / (n1 + n2 + 2 - i);

        double ans = temp;
        for(int i=1; i<=m2; i++) {
            temp = temp * (m1 + i)/i * (n2 + 2 - i)/(n1 + n2 - m1 + 2 - i);
            ans += temp;
        }

        cout << ans << "\n";
    }
}

 

수학 문제 중에서도 특히 아이디어가 중요한 조합론 문제이기에 풀이 코드는 아주 단순합니다.

풀이 과정은 위에서 모두 언급했기 때문에 더 이상 설명할 부분이 없습니다.

 

 

 

맞은 사람 11명 중에서도 준수한 기록으로 통과할 수 있었습니다.

배열을 아예 사용하지 않고 풀었기에 메모리는 가장 적게 사용했네요.

 

 

 

아무튼 위와 같이 풀이가 가능하다는 것을 정리해보았습니다.

질문 사항 있으시면 댓글로 남겨주시면 답변해드리겠습니다.