[DP] 백준 11051 이항계수2

이항계수 2 팩토리얼 값 미리 다이나믹으로 구해두고 나눠서 풀려고 했는데

나머지 연산이라 n은 본래 큰 값이지만 나머지는 n-m의 값보다 작을 수 있다. 해결할 방법이 지금 생각나지 않음.

#include <iostream>

#include <algorithm>

#include <cstring>

#include <limits.h>

#include <stack>

using namespace std;

typedef long long ll;

ll stb[10001]; // single table

ll sche[100001]; // single cache

int tb[1001][1001];

int cache[1001][1001];

int n,m;

int facto(int num) {

       cout << num << endl;

       if (num == 0) {

              return 1;

       }

       if (sche[num] != -1) {

              return sche[num];

       }

       sche[num] = ((num%10007) * (facto(num - 1)%10007))%10007;

       cout << sche[num] << endl;

       return sche[num];

}

int main(void) {

       memset(sche, -1, sizeof(sche));

       cin >> n >> m;

       if (n == m || m == 0) {

              cout << 1 << endl;

              return 0;

       }

       facto(n);

       cout << sche[n] / sche[n - m] / sche[m] ;

       

       return 0;

}

이게 해법 곱하기와 나누기 말고 합으로 해결 가능했다. 

#include <iostream>

#include <algorithm>

#include <cstring>

#include <limits.h>

#include <stack>

using namespace std;

typedef long long ll;

ll stb[10001]; // single table

ll sche[100001]; // single cache

int tb[1001][1001];

int cache[1001][1001];

int n,m;

int main(void) {

       

       cin >> n >> m;

       if (n == m || m == 0) {

              cout << 1 << endl;

              return 0;

       }

       cache[0][0] = cache[1][0] = cache[1][1] = 1;

       for (int i = 2; i <= n; ++i) {

              cache[i][0] = cache[i][i] = 1;

              for (int j = 1; j <= i-1; ++j) {

                     cache[i][j] = cache[i - 1][j - 1]%10007 + cache[i - 1][j]%10007;

              }

       }

       cout << cache[n][m]%10007;

       

       return 0;

}