어떤 문제인가?

메모이제이션을 이용해 이항계수를 구하는 문제.

없어도 좋고 있어도 좋고

메모이제이션(또는 타뷸레이션)은 안써도 된다. 고전적인 풀이 방식으로도 충분히 해결할 수 있다. 분자를 분모로 나누는거.

#include <stdio.h>
#include <stdlib.h>

unsigned g(unsigned a, unsigned b) {
    if(b==0) return a;
    return g(b, a%b);
}
int main() {
    unsigned N,K,i,j,S=1,t,*k1,*k2;
    scanf("%d %d", &N, &K);
    k1=(unsigned*)calloc(4,N-K);
    k2=(unsigned*)calloc(4,N-K);
    for(i=N;i>K;i--) k1[N-i]=i;
    for(i=N-K;i>0;i--) k2[N-K-i]=i;
    for(i=0;i<N-K;i++) {
        for(j=0;j<N-K;j++) {
            if(k2[i]==1) break;
            t=g(k1[j],k2[i]);
            if(t>1) {
                k1[j]/=t;
                k2[i]/=t;
            }
        }
    }
    for(i=0;i<N-K;i++) S=S*k1[i]%10007;
    printf("%d", S);
}

남들의 풀이

그러나 깔끔하게 풀려면 역시 메모이제이션을 쓰는게 낫다.
또한 파스칼의 삼각형 공식을 쓰면 더 빠르게 구할 수 있다.

#include <stdio.h>
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]);
}

osori_1010님의 풀이
-> https://www.acmicpc.net/source/21988829

참고한 문헌

1. 파스칼의 삼각형에 대한 간단한 설명
   -> https://m.blog.naver.com/saomath/221948595533