[백준 16395] 파스칼의 삼각형

문제출처: https://www.acmicpc.net/problem/16395

풀이

파스칼의 삼각형같은 이항계수의 성질을 이용하는 문제는 dp로 접근하는게 제일 쉬운 것 같습니다.

각 행의 맨 왼쪽 값을 1로 고정시켜놓고 n+1Cr+1=nCr+nCr+1 의 성질을 이용하여 dp식을 세웠습니다.

*각 행의 맨 오른쪽 값1은 최초의 값 1설정 후 dp계산시 저절로 1로 고정된 상태가 됩니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, k;
int dp[31][31];
int main()
{
    cin >> n >> k;
    for (int i = 0; i < 31; i++)
    {
        dp[i][0] = 1;
    }
    for (int i = 1; i < 31; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    cout << dp[n-1][k-1] << endl;
    
}

결과