[13251] 조약돌 꺼내기

✔ 조약돌 꺼내기

[백준 13251]

문제 분석하기

조합을 이용하여 색깔별 조약돌의 개수에서 K를 뽑을 수 있는 경우의 수를 구한 후, 전체 돌에 관해 N개를 뽑는 경우의 수로 나눔

손으로 풀어보기

1. 색깔별 조약돌의 개수를 배열 D에 저장하고, 전체 조약돌 개수를 변수 T에 저장
2. 한 색깔의 조약돌만 뽑을 확률을 색깔별로 구함
   • 예) 전체 조약돌 개수가 18개이고, 5개의 조약돌이 있는 색깔만 2개 뽑을 확률 : 5/18 * 4/17 = 0.06535947712418301
3. 각각의 확률을 더해 정답으로 출력

슈도코드 작성하기

T(전체 조약돌 개수) M(색의 종류) K(선택 조약돌 개수)
probability(색깔별 확률 저장하기 배열)
D(각 색깔별 조약돌 개수 저장하기 배열)
for(i -> M만큼 반복하기) {
    D 배열에 각 조약돌 개수 저장하기
    T 변수에 조약돌의 개수 더하기
}
K 변수 받기
for(i -> M만큼 반복하기) {
    if(현재 색깔의 조약돌의 개수가 선택해야 할 개수보다 크면)
        for(j -> K만큼 반복하기) {
            i 색깔을 뽑을 확률 = i 색깔을 뽑을 확률 * 현재 색깔 개수 - K / 전체 색깔 개수 - K;
        }
        정답에 현재 색깔을 모두 뽑을 확률 더하기
    }
    정답 출력하기
}

코드 구현하기

/**
 * 13251) 조약돌_꺼내기
 */
public class D080_13251 {
    static int T, M, K;
    // probability(색깔별 확률 저장하기 배열)
    static double probability[] = new double[51];
    // D(각 색깔별 조약돌 개수 저장하기 배열)
    static int D[] = new int[51];
    static double answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // M(색의 종류)
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        // T(전체 조약돌 개수)
        T = 0;
        for (int i = 0; i < M; i++) {
            // D 배열에 각 조약돌 개수 저장하기
            D[i] = Integer.parseInt(st.nextToken());
            // T 변수에 조약돌의 개수 더하기
            T += D[i];
        }
        st = new StringTokenizer(br.readLine());
        // K(선택 조약돌 개수)
        K = Integer.parseInt(st.nextToken());
        answer = 0.0;
        for (int i = 0; i < M; i++) {
            // 현재 색깔의 조약돌의 개수가 선택해야 할 개수보다 크면
            if (D[i] >= K) {
                probability[i] = 1.0;
                for (int k = 0; k < K; k++) {
                    // i 색깔을 뽑을 확률 = i 색깔을 뽑을 확률 * 현재 색깔 개수 - K / 전체 색깔 개수 - K;
                    probability[i] *= (double) (D[i] - k) / (T - k);
                }
                // 정답에 현재 색깔을 모두 뽑을 확률 더하기
                answer += probability[i];
            }
        }
        // 정답 출력하기
        System.out.println(answer);
    }
}