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

문제 설명

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

 

 

접근 방법 - 조합을 활용한 확률 연산 응용문제

백준의 13251번 문제는 조합을 활용하여 확률에 대한 경우의 수를 고려하면서 연산을 진행해야 하는 문제이다.

해당 문제는, 조약돌의 색상과 각각의 개수가 입력으로 주어질 때 K번 조약돌을 뽑을 경우 모두 같은 색상일 확률을 구하여 이를 정답으로 출력해야 하는 문제이다.

이때 출력 조건을 확인해 보면, 소수점 9번째 자리 이상으로 정밀하게 정답을 출력해야 한다는 점을 알 수 있다.

 

우선 학창 시절에 잠깐 들어봤을 법한 조합의 개념부터 먼저 훑어볼 필요가 있다.

조합이란, 서로 다른 n개에서 순서를 고려하지 않고 r개를 택하는 경우의 수를 의미한다.

조합의 기본적인 공식은 아래와 같다.

 

필자는 위 공식을 참고하여, 각 색상의 조약돌에 대한 (해당 색상의 조약돌 하나를 뽑는 경우) / (전체 조약돌 중 하나를 뽑는 경우)를 K번 연산하고 이들을 모두 곱하였다.

그리고 각 색상에 대한 위 곱 연산 결과들을 모두 합하여, 이를 정답으로 출력하게끔 하였다.

위 원리를 적용한 구체적인 예시를 문제의 예제 입출력과 함께 아래에 정리해 보았다.

[예제 입출력 1]
M = 1
N = 13
K = 8

(편의상, 조약돌의 색상을 빨강으로 가정한다.)
* 전체에서 조약돌을 하나씩 8번 뽑았을 때, 모두 빨강 조약돌일 확률은 아래와 같다.

=> 색상이 하나이기 때문에, 정답은 1이라 볼 수 있다.

[예제 입출력 3]
M = 3
N = 5, 6, 7
K = 2

(편의상, 조약돌의 색상을 각각 빨강, 파랑, 노랑으로 가정한다.)
* 전체에서 조약돌을 하나씩 2번 뽑았을 때, 모두 빨강 조약돌일 확률은 아래와 같다.

* 전체에서 조약돌을 하나씩 2번 뽑았을 때, 모두 파랑 조약돌일 확률은 아래와 같다.

* 전체에서 조약돌을 하나씩 2번 뽑았을 때, 모두 노랑 조약돌일 확률은 아래와 같다.

=> 각 색상에 대한 확률 결과를 모두 합하면, 정답은 약 0.30065...이라 볼 수 있다.

 

필자는 위 원리를 기반으로 코드를 작성하여 문제 해결을 시도해 보았다.

보다 자세한 설명을 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 조약돌의 색상 개수(m)를 입력받는다.

 

2) 각 색상의 조약돌 개수를 저장할 벡터 stone을 미리 선언해 둔다.

그리고 총 조약돌의 개수를 저장할 변수 sum을 0으로 초기화하여 미리 선언해 둔다.

 

3) m의 크기만큼, 반복문을 수행하여 각 색상의 조약돌 개수(num)를 하나씩 입력받는다.

입력을 받을 때마다, num 값을 stone의 요소로 삽입하고 sum에 값을 더하도록 한다.

 

4) 조약돌을 뽑는 횟수(k)를 입력받는다.

 

5) k번 뽑은 조약돌이 모두 같은 색상일 확률을 저장할 변수 result를 0으로 초기화하여 미리 선언해 둔다.

(확률 정보는 실수형 정보이기 때문에, 자료형은 double로 설정하였다.)

 

6) m의 크기만큼, 반복문을 수행하여 각 조약돌 색상에 대한 확률 연산을 수행한다.

- k번 조약돌을 뽑을 때 모두 현재 색상의 조약돌이 나올 확률을 임시로 저장할 변수 tmp를 1로 초기화하여 선언해 둔다.

(조약돌을 하나씩 뽑을 때마다의 확률을 tmp에 곱해나갈 예정이기 때문에, 우선은 1로 초기화해 둔다.)

- 다른 반복문을 통해, 조약돌을 하나씩 뽑아나갈 때의 확률 연산을 진행하도록 한다.

현재 색상의 조약돌 개수(stone[i]-j)를 현재까지의 전체 조약돌 개수(sum-j)로 나누고, 이 결과를 tmp에 곱하도록 한다.

- 위 연산이 완료되었다면, 최종적으로 저장된 현재 tmp의 값이 곧 현재 색상의 조약돌만 나오는 확률에 해당되기 때문에 이를 result에 더해주도록 한다.

 

7) 최종적으로 저장된 result의 값을 정답으로 출력한 뒤, 실행을 종료한다.

(문제의 조건을 만족하기 위하여, 필자는 아래 구문을 통해 정답을 소수점 9번째 자리까지 출력하게끔 하였다.)

cout << fixed;
cout.precision(9);

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

//백준 13251번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	cout << fixed;
	cout.precision(9);
	
	int m;
	cin >> m;

	vector<double> stone;
	int sum = 0;
	for (int i = 0; i < m; i++) {
		double num;
		cin >> num;

		stone.push_back(num);
		sum += num;
	}

	int k;
	cin >> k;

	double result = 0;
	for (int i = 0; i < m; i++) {
		double tmp = 1;
		for (int j = 0; j < k; j++) {
			tmp *= (stone[i] - j) / (sum - j);
		}
		result += tmp;
	}

	cout << result << endl;
}

 

제출 결과

(2025.11.02 백준 13251번 문제 제출 결과)