[알고리즘] 조합 C++로 구현하기

 

일반적인 for문의 경우, 연산량이 너무 많기 때문에 계산이 제대로 처리되지 않는다.

그래서 곱하면서 나누는 전략이나, 파스칼의 삼각형으로 풀어야 한다.

 

 

다음은 nCm을 출력하기 위한 두 종류의 코드이다.

 

1. for문으로 풀기

#include <iostream>
using namespace std;

// 이걸로 30이상 계산하려고 하면 for문이 터져버린다
int factorial(int n){
  int result = 1;
  
  for(int i = 1; i <= n; i++){
    result *= i;
  }
  
  return result;
}
int main() {

  //Please Enter Your Code Here
  int n, m;
  cin >> n >> m;
  
  unsigned long long  res = 1;
  //int res = 1;
  
  // 0부터 m까지 곱하면서 동시에 나눈다.
  for(int i = 0; i < m; i++){
    res *= n-i;
    res /= i+1;
  }
  
  cout << res << endl;

  return 0;
}

 

 

2. 파스칼의 삼각형을 구현해서 풀기

 

파스칼 삼각형 이론과는 달리, 직각삼각형 모양으로 구현하는 게 훨씬 편하다.

 

#include <iostream>
using namespace std;

int main()
{
  unsigned long pascal[32][32];
  int n, m;
  cin >> n >> m;
  
  // 0으로 맞춰줌
  for(int i = 0; i <=n ;i++){
    for(int j = 0; j <=n; j++){
      pascal[i][j] = 0;
    }
  }
  // 테두리는 1로 초기화
  for(int i = 0; i <= n+1; i++){
    pascal[i][0] = 1;
    pascal[n][i] = 1;
    pascal[i][i] = 1;
  }
  // 파스칼의 삼각형 구현
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= i; j++){
      pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
    }
  }

  
  cout << pascal[n][m] << endl;
}