[9일차][DP] 이항계수 구하기

- 문제 설명

(x+y)^3을 하면

x^3 + 3x^2y + 3xy^2 + y^3 이 나온다

이 때 x^2y의 이항계수는 3이다

이런식으로 (x+y)^n을 할 때 x^ay^b의 이항계수를 구하는 문제

- 입력

1 // 테스트 케이스

2 1 1 // n, a, b

- 출력

#1 2 // 테스트케이스, 이항계수

- 입력 예시

3
2 1 1
3 2 1
5 3 2

- 출력 예시

#1 2
#2 3
#3 10

- 코드

#include "stdio.h"

int N;

long long int binomial[71][71]; // 이항계수 배열

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        int a, b;

        scanf("%d %d %d",&N,&a,&b);

        

        // 파스칼의 삼각형의 1인 부분 채우기(x^n과 y^n의 이항계수는 항상 1이기 때문)

        for(int i=0;i<=N;i++)

        {

            binomial[i][0] = 1;

            binomial[i][i] = 1;

        }

        // 파스칼의 삼각형 채우기

        for (int i = 2; i<=N;i++)

        {

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

            {

                binomial[i][j] = binomial[i-1][j-1] + binomial[i-1][j]; // 바로 위랑 왼쪽위를 더하여 이항계수를 구함

            }

        }

        printf("#%d %lld\n", tc,binomial[N][a]); // 몹시 커질수 있다하여 long long으로 출력

    }

    return 0;

}

- 파스칼의 삼각형

1

1 2 1

1 3 3 1

1 4 6 4 1

위와 같이 이항계수를 구할 수 있다.