[BaekJoon/백준] 11051번 파스칼의 삼각형

 

새벽이라 그런거니 나자신?

일단 맨 처음 방식은, 동적계획법으로 팩토리얼을 사용해서 구했다가 틀렸다. 생각해보니 너무 간단하게 생각했던 것 같다.

당연히 오버플로우가 났다.

 

 

두번째로 파스칼의 삼각형을 사용했다.

https://nackwon.tistory.com/55

nCk 라고 봤을 때, 이런 규칙이 있다.

‣  k = 0일때, nCk = 1

‣  n = k일때, nCk = 1

‣ 그 외, nCk = (n-1)Ck + (n-1)C(k-1)

 

이를 토대로 코딩하면 되는데

#include <stdio.h>
int N;
int K;
int D[1001][1001];
int main()
{
    scanf("%d %d", &N, &K);
    
    //1C0 부터 고려하기에, i는 1부터, j는 0부터
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j <= i; j++) {
            
            if(j == 0 || i == j)
                D[i][j] = 1;
            else
                D[i][j] = (D[i - 1][j] + D[i - 1][j - 1]) % 10007;
            
        }
    }
    
    printf("%d", D[N][K]);
    
}

문제에서 주어지는 조건인 %10007을 위처럼 넣어주면 된다.

처음에는, A + B % 10007 이렇게... 괄호를 안붙이고 계속 제출하면서 왜틀렸는지 모르겠더라.. (A + B) % 10007 이렇게 해줘야하는데..

 

...........수고