백준 온라인 저지(Baekjoon Online Judge) - 16395 : 파스칼의 삼각형

 

https://www.acmicpc.net/problem/16395

16395번: 파스칼의 삼각형

 

#include <iostream>
#include <vector>

using namespace std;

// 이항 계수 계산 함수
int binomialCoefficient(int n, int k) {
    // 계산 결과를 저장할 동적 배열 생성
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

    // 초기값 설정
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, k); j++) {
            if (j == 0 || j == i)
                dp[i][j] = 1;
            else
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }

    // 이항 계수 값 반환
    return dp[n][k];
}

int main() {
    int n, k;
    cin >> n >> k;

    int res = binomialCoefficient(n - 1, k - 1);

    cout << res << endl;

    return 0;
}

 

 

파스칼의 삼각형 문제: 이항 계수 계산
파스칼의 삼각형은 이항 계수를 삼각형 형태로 배열한 것으로, 이항 계수를 효율적으로 계산하기 위한 방법입니다. 이 문제에서는 주어진 n과 k에 대해 파스칼의 삼각형에서 n번째 행의 k번째 수를 구하는 문제입니다.

문제 해결 방법
이 문제를 해결하기 위해 다이나믹 프로그래밍(Dynamic Programming)의 개념을 활용하여 이항 계수를 계산하는 함수를 작성합니다. 이를 위해 다음과 같은 단계를 따릅니다.

1. 먼저, 계산 결과를 저장할 동적 배열 dp를 생성합니다. dp는 2차원 배열로 크기는 (n+1) × (k+1)입니다. 각 요소는 0으로 초기화됩니다.

2. 다음으로, 초기값을 설정합니다. 모든 dp[i][0]와 dp[i][i]는 1로 설정합니다. 이는 첫 번째 열과 각 행의 대각선 요소에 해당합니다.

3. 파스칼의 삼각형을 채워나가기 위해 점화식을 사용합니다. dp[i][j]는 dp[i-1][j-1]과 dp[i-1][j]의 합으로 계산됩니다. 이는 위 행의 인접한 두 수의 합이므로, 이항 계수를 계산하는 방식과 일치합니다.

4. 마지막으로, dp[n][k] 값을 반환합니다. 이는 n번째 행의 k번째 수에 해당합니다.

 

* 해당 게시물은 ChatGPT를 참고하여 작성되었음을 알립니다.