[BOJ 백준] 조약돌 꺼내기(13251) C++

 

링크 : https://www.acmicpc.net/problem/13251

13251번: 조약돌 꺼내기

 

문제 설명 : 

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

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

 

입력 : 

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

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

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

출력 : 

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

 

예제 입력 : 

3
5 6 7
2

예제 출력 : 

0.035028830818304504

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 조약돌 꺼내기 13251
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (50+3)

using namespace std;

int M, K;	// M - 조약돌 색상 종류 / K - 랜덤뽑기 개수

double stoneByColor[MAX];
double percent[MAX];

double total, ans;
int cnt;


int main() {
	// 1. 입력
	//freopen("input.txt", "r", stdin);
	scanf("%d", &M);

	// 2. 컬러별 돌 개수 입력받을때 전체 개수 카운트
	int input;
	for (int i = 0; i < M; i++) {
		scanf("%d", &input);
		stoneByColor[i] = (double)input;
		total += stoneByColor[i];
	}

	// 3. 확률 계산
	scanf("%d", &K);
	double tmp;
	for (int i = 0; i < M; i++) {
		
		// ** 예외 조건 
		if (stoneByColor[i] < K) continue;

		tmp = 1.0;
		for (int j = 0; j < K; j++) {
			tmp *= (stoneByColor[i] - j) / (total - j);
		}
		percent[i] = tmp;
	}

	for (int i = 0; i < M; i++) {
		ans += percent[i];
	}
	
	// 4. 출력 10-9까지 허용
	printf("%.11lf", ans);
	return 0;
}
#endif