[백준 15489번] 파스칼 삼각형

문제 링크: https://www.acmicpc.net/problem/15489

15489번: 파스칼 삼각형

<문제 풀이> 다이나믹 프로그래밍(DP), 수학

 

 

파스칼 삼각형을 아래 그림과 같이 왼쪽으로 정렬된 형태로 생각하면 2차원 배열로 쉽게 표현할 수 있습니다.

그러면 맨 왼쪽을 모두 1로 채운 뒤 ㄱ자 모양으로 파스칼 삼각형 DP 배열을 채우면 됩니다.

 

 

 

 

<C++소스코드>

#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
 
int R, C, W;
 
int dp[32][32];
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> R >> C >> W;
 
    for (int i = 1; i <= 31; i++) {
        dp[i][1] = 1;
    }
 
    for (int i = 1; i <= 29; i++) {
        for (int j = 1; j <= 29; j++) {
            dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < W; i++) {
        for (int j = 0; j <= i; j++) {
            ans += dp[R + i][C + j];
        }
    }
 
    cout << ans;
 
    return 0;
}