조합 백준 2407번 c++

문제 링크 

 

조합을 하나씩 써 보면 그 값이 파스칼의 삼각형과 똑같이 나오는 것이 보인다. 

nCm == n-1 C m-1  + n-1 C m 

 

       1C0, 1C1

   2C0, 2C1, 2C2

3C0, 3C1, 3C2, 3C3

 

0개를 고를때와 n개중에 n개를 전부 고를 때는 값이 항상 1이다. 

 

조합 계산할 때 숫자가 커지니까 string 끼리의 계산이 필요했다. 

일의 자리끼리 계산 하고,  10으로 나눈 나머지를 일의자리로 저장한다.

일의 자리 계산 결과를 나누기 10하면, 올림수가 발생했는지 판단할 수 있다. 

 

 

"맞았습니다" 코드 링크 

#include <bits/stdc++.h>
using namespace std;

int n, m;
string dp[102][102];

string numAdd(string n1, string n2){
  string answer = "";
  int sum = 0;
  int len = max(n1.size(), n2.size());

  for(int i = 0; i < len || sum; i++){ // 일의 자리를 덧셈한다.
    if(n1.size() > i) sum += (n1[i] - '0');
    if(n2.size() > i) sum += (n2[i] - '0');
    answer += ((sum % 10) + '0');
    sum /= 10;
  }

  return answer;
}

string combination(int n, int m){
  if(n == m || m == 0) return "1";

  string &res = dp[n][m];
  if(res != "") return res;

  res = numAdd(combination(n-1, m-1), combination(n-1, m));
  return res;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  string ans = combination(n, m);
  reverse(ans.begin(), ans.end());
  cout << ans;
  return 0;
}