문제

문제 링크

문제 접근

  • 나눗셈에 대한 모듈러 연산은 (a/b)%k != (a%k)/(b%k)으로 이항계수에 모듈러를 적용하기 쉽지 않다.
  • 유클리드 호제법, 페르마의 소정리 등을 보다가 결국 파스칼 삼각형을 알게 되었다.
  • 다음 이항 계수 문제 접근 링크를 보고 이항계수를 dp를 이용해서 구하는 방법을 알 수 있었다.

코드

#include <cstdio>
int n, k, c[1001][1001];
int main(){
    scanf("%d %d", &n, &k);
    c[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            if(j-1 < 0)c[i][j] = c[i-1][j];
            c[i][j] = (c[i-1][j] + c[i-1][j-1])%10007;
        }
    }
    printf("%d", c[n][k]);
}

느낀점

  • 디피 굳!!