백준 16395번 : 파스칼의 삼각형 (C 언어)

Code:

#include <stdio.h>
 
int dp[31][31] = { 0, };
 
int binomial(int n, int r)
{
    for (int i = 0; i < n ; i++)
    {
        int temp = (i > r) ? r : i;
        for (int j = 0; j <= temp; j++)
        {
            if (j == 0 || i == j)
            {
                dp[i][j] = 1;
            }
            else
            {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }
    return dp[n-1][r-1];
}
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int cnt = binomial(n, k);
    printf("%d", cnt);
}

문제 설명: 주어진 문제에서는 파스칼의 삼각형을 사용하여 이항 계수를 계산하고, n번째 행에서 k번째 수를 출력하는 프로그램을 작성해야 합니다. 파스칼의 삼각형은 다음과 같이 생성됩니다.

1. 첫 번째 행은 1로 시작합니다.
2. 두 번째 행부터는 양 끝의 값이 1이고, 나머지 수는 바로 위 행의 인접한 두 수를 더한 값입니다.
3. n번째 행의 k번째 수는 C(n-1, k-1)로 계산됩니다.

코드 설명:

1. int dp[31][31] = { 0, };: 2차원 배열 dp를 선언하고 초기화합니다. dp[i][j]는 i번째 행에서 j번째 수를 저장하기 위한 배열입니다.
2. int binomial(int n, int r): 이항 계수 C(n-1, k-1)을 계산하는 함수를 정의합니다. 이 함수는 파스칼의 삼각형을 생성하면서 값을 계산합니다.
   • 두 개의 반복문을 사용하여 파스칼의 삼각형을 생성합니다. 외부 반복문은 행을 나타내고, 내부 반복문은 해당 행의 열을 나타냅니다.
   • 각 위치 (i, j)에서, 만약 j가 0이거나 i와 j가 같다면, 그 값은 1입니다.
   • 그 외의 경우, 현재 위치 (i, j)의 값은 바로 위 행의 인접한 두 수 (i-1, j-1)과 (i-1, j)을 더한 값입니다.
   • 최종적으로 dp[n-1][r-1]을 반환하여 이항 계수를 구합니다.