1010 다리놓기

#include<iostream>
#include<vector>
#include<algorithm>

int bi[30][30];

int binary(int n, int r) {
if (bi[n][r] > 0)return bi[n][r];
if (r == 0 || r == n)return bi[n][r]=1;
return bi[n][r]=binary(n - 1, r - 1) + binary(n - 1, r);
}


using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int c;
cin >> c;
for (int i = 0; i < c; i++) {
int r, n;
cin >> r >> n;
cout <<binary(n, r)<<"\n";


}


}

이항계수를 계산하면 되는 경우의 수 문제이다.

nCr함수를 만들어서 n*n-1*...*n-r/r!으로 구현을 하니 n이 조금만 커져도 오버플로우가 나서 이걸 스트링으로 변환해서 연산하기보다 점화식을 쓰는게 좋을꺼 같아서 점화식으로 바꿈

nCr = n-1Cr-1+n-1Cr 을 이용해서 재귀함수를 만들었지만 아직까지도 O(n!)의 수행시간이 걸려서

메모이제이션을 이용해서 수행시간을 줄였다.

 

+나머지 연산 분배법칙

(a+b)%c =(( a%c)+(b%c))%c

(a*b)%c =(( a%c)*(b%c))%c

(a-b)%c =(( a%c)-(b%c)+c)%c ->계산과정에서 음수로 나올수가있어서 c를 한번 더해준다고 함