글 읽기 - 13251 질문

dlrkddnr2718 1년 전 0

문제를 푼 방식은 다음과 같습니다.

같은 색의 조약돌이 a, b, c개 있다고 가정하겠습니다.

그리고 여기서 k 개의 조약돌을 뽑는다고 가정하겠습니다.

그러면 같은 색의 조약돌을 뽑을 확률은

aCk + bCk + cCk / (a + b + c) C k 입니다.

문제에서 뽑는 조약돌의 개수를 k >= 1로 제한했기 때문에 0으로 나누는 경우도 없고,

위의 예시에서 a, b, c < k 인 경우는, aCk, bCk, cCk가 각각 모두 0으로 처리되기 때문에 오류를 내지 않는다고 생각합니다.

그리고 문제의 예시로 주어진 값들도 모두 오차 범위 내에서 출력한다고 생각하는데, 제출하면 틀렸습니다가 나옵니다.

반례가 무엇인지, 제 코드에서 어느 부분이 잘못되었는지 알려 주시면 정말 감사드리겠습니다.

#include <iostream>
#include <vector>
using namespace std;
int factorial(int);
int combination(int, int);
int permutation(int, int);
int main()
{
    int color_num, random_pick_num; /// 조약돌의 색상의 개수를 저장하는 변수와, 몇 개의 조약돌을 랜덤하게 뽑을지 결정한다.
    int total_pebble_num = 0; /// 정체 조약돌의 개수를 저장할 변수 설정.
    int same_color_number_of_case = 0; /// 같은 색상의 조약돌을 뽑는 경우의 수를 저장.
    double same_color_probability; /// 같은 색상의 조약돌을 뽑을 확률.
    cin >> color_num;
    vector<int> pebble{}; /// 각 조약돌의 색상별 개수를 저장할 변수.
    for(int i = 0; i < color_num; i++)
    {
        int pebble_num;
        cin >> pebble_num;
        total_pebble_num += pebble_num;
        pebble.push_back(pebble_num);
    }
    cin >> random_pick_num; /// 몇 개의 조약돌을 뽑을지 저장하는 변수.
    for(int i = 0; i < color_num; i++)
    {
        same_color_number_of_case += combination(pebble[i], random_pick_num);
    }
    cout.precision(20);
    same_color_probability = double(same_color_number_of_case) / double(combination(total_pebble_num, random_pick_num));
    cout << same_color_probability;
    return 0;
}
int permutation(int n, int r)
{
    int result = 1;
    for(int i = 0; i < r; i++)
    {
        result *= n;
        n--;
    }
    return result;
}
int factorial(int n) /// 팩토리얼을 계산하는 함수.
{
    int i;
    int result = 1;
    for(i = 1; i <= n; i++)
    {
        result *= i;
    }
    return result;
}
int combination(int n, int r) /// 조합 값을 계산하는 함수.
{
    return (permutation(n, r) / factorial(r));
}

dlrkddnr2718 1년 전 0

이 방법으로는, 무조건 오버플로우가 발생합니다

경우에 따라서, 2500 C 1100 등을 계산해야 할 수도 있기 때문입니다.

그래서 큰 틀에서 이 방식으로, 세부적인 내용을 조금 바꾸어서 제출하여 맞았습니다.

저와 비슷한 문제로 고민하시는 분들은 도움이 되었으면 좋겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

13251 질문

dlrkddnr2718 1년 전 0

dlrkddnr2718 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말