nCr 코드 (Combination)

처음 보면 수학에서의 단순 조합 문제

고등학교 확통 과목에서 배운대로 구현하면 된다.

 

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

nCm은 이런식으로 나오는데, 

이를 일반화하면 arr[i][j] = arr[i-1][j-1] + arr[i-1][j]로 세울 수 있다.

 

아래는 백준 1010번 정답 코드

#include <iostream>
using namespace std;
int arr[31][31];
int main() {
    int n, a, b;
    cin >> n;
    for(int i=1; i<30; i++){
        for(int j=0; j<=i; j++){
            if(j==0 || j==i){
                arr[i][j]=1;
            }
            else if(j==1){
                arr[i][j]=i;
            }
            else{
                arr[i][j]=arr[i-1][j]+arr[i-1][j-1];
            }
        }
    }
    while(n--){
        cin >> a >> b;
        cout << arr[b][a] << "\n";
    }
}