[BOJ] 2407번: 조합

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

2407번: 조합

문제

nCm을 출력한다.

 

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

 

출력

nCm을 출력한다.

---

풀이

조합의 성질인 _n C _r + _n C _r+1 = _n+1 C _r+1 을 이용한다.

그런데 조합의 결과값이 int 범위를 벗어나므로 string 배열을 사용하여 계산해야 한다.

string도 vector처럼 push와 pop을 할 수 있고 reverse함수를 이용하여 배열을 역으로 바꿀 수 있다.

 

 

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n, m;
string com[101][101];

string add(string num1, string num2) {
  string num = "";
  int sum = 0;

  while(!num1.empty() || !num2.empty() || sum) {
    if(!num1.empty()) {
      sum += num1.back() - '0';
      num1.pop_back();
    }
    if(!num2.empty()) {
      sum += num2.back() - '0';
      num2.pop_back();
    }
    num.push_back((sum%10)+'0');
    sum /= 10;
  }

  reverse(num.begin(), num.end());
  return num;
}

string find(int a, int b) {
  if(b==0 || b==a) return "1";

  string &num = com[a][b];
  if(num != "") return num;
    
  num = add(find(a-1,b-1),find(a-1,b));
  return num;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  cin >> n >> m;
  cout << find(n, m);
  return 0;
}

처음에 int 배열을 사용하여 풀었지만 int 범위를 벗어날 수 있다는 것을 알았다.

 

결과