[JAVA] 조약돌 꺼내기_13251

출처: https://www.acmicpc.net/problem/13251

13251번: 조약돌 꺼내기

 

 

조약돌 꺼내기 성공스페셜 저지

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

3142

1233

1023

41.518%

문제

효빈이의 비밀 박스에는 조약돌이 N개 들어있다. 조약돌의 색상은 1부터 M까지 중의 하나이다.

비밀 박스에서 조약돌을 랜덤하게 K개 뽑았을 때, 뽑은 조약돌이 모두 같은 색일 확률을 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 M (1 ≤ M ≤ 50)이 주어진다.

둘째 줄에는 각 색상의 조약돌이 몇 개 있는지 주어진다. 각 색상의 조약돌 개수는 1보다 크거나 같고 50보다 작거나 같은 자연수이다.

셋째 줄에는 K가 주어진다. (1 ≤ K ≤ N)

출력

첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.

예제 입력 1 복사

1
13
8

예제 출력 1 복사

1.0

예제 입력 2 복사

2
5 7
1

예제 출력 2 복사

1.0

예제 입력 3 복사

3
5 6 7
2

예제 출력 3 복사

0.3006535947712418

예제 입력 4 복사

5
12 2 34 13 17
4

예제 출력 4 복사

0.035028830818304504

출처

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: goooora

알고리즘 분류

• 수학
• 조합론
• 확률론

 

 

 

---

import java.util.Scanner;
import java.util.Arrays;

public class Main
{
    private static Scanner s = new Scanner(System.in);
    
	public static void main(String[] args) {
	    
	    int M = s.nextInt(); // 조약돌 색상 수
	    int[] stones = new int[M]; //각 색상별 조약돌 수
	    int totalCount = 0; // 조약돌의 총 갯수
	    
	    for(int i=0; i<M; i++) {
	        stones[i] = s.nextInt();
	        totalCount += stones[i];
	    }
	    
	    int K = s.nextInt(); // 몇 번 뽑을지 선택
	    
	    // 가능한 모든 경우의 수 구하기
	    double totalSituation = 1;
	    for(int i=0; i<K; i++) {
	        totalSituation *= (totalCount-i);
	    }
	    
	    // 같은 색상이 나오는 경우의 수 구하기
	    double sum = 0;
	    for(int i=0; i<M; i++) {
	        // 애초에 목표한 돌의 갯수보다 수가 작으면 SKIP
	        if(stones[i] < K) continue;
	        
            // 아니면 경우의 수 구해서 합하기
	        double tmp = 1;
	        for(int j=0; j<K; j++) {
	            tmp *= (stones[i]-j);
	        }
	        sum += tmp;
	    }
	    
	    System.out.println(sum / totalSituation);
	}
}