[백준][C++]13251번 조약돌 꺼내기

문제

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

13251번: 조약돌 꺼내기

 

 

풀이

조합(Combination) 알고리즘

조합(Combination) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int M, N = 0, K;
  cin >> M;

  vector<int> count(M + 1);
  for(int i = 0; i < M; i++)
  {
    cin >> count[i];	// 각 조약돌 개수 저장하기
    N += count[i];	// 조약돌의 개수 더하기
  }

  cin >> K;

  double result = 0.0;
  for(int m = 0; m < M; m++)
  {
    double percent = 1.0;
    if(count[m] >= K)	// 선택 조약돌 개수보다 현재 색 조약돌 개수가 적으면 모두 같은 색으로 뽑힐 확률은 0
    {
      for(int i = 0; i < K; i++)
      {
        percent *= (double)(count[m] - i) / (N - i);
      }
      result += percent;	// 정답에 현재 색깔을 모두 뽑을 확률 더하기
    }
  }

  cout.precision(9);	// 오차 범위 내 출력을 위한 소수점 자릿수 설정
  cout << result;	// 정답 출력하기

  return 0;
}

 

 

오답

• 한 색깔의 조약돌만 뽑을 확률을 색깔별로 모두 구한다.
  • 선택 조약돌 개수보다 현재 색 조약돌 개수가 적으면 모두 같은 색으로 뽑을 확률은 0

 

#include <iostream>
using namespace std;

static int M, K, T;
static int D[51];
static double probability[51];
static double ans = 0.0;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> M;

  for(int i = 0; i < M; i++)
  {
    cin >> D[i];
    T += D[i];
  }

  cin >> K;

  for(int i = 0; i < M; i++)
  {
    if(D[i] >= K)
    {
      probability[i] = 1.0;

      for(int k = 0; k < K; k++)
      {
        probability[i] *= (double)(D[i] - k) / (T - k);
      }
    }
    ans += probability[i];
  }

  cout << fixed;
  cout.precision(9);  // 오차 범위 내 출력을 위한 소수점 자릿수 설정
  cout << ans;
}