[백준 15489번] 파스칼 삼각형 (C++)

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

15489번: 파스칼 삼각형

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int R, C, W, result;
int dp[31][31];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> R >> C >> W;

    for(int i=1; i<=30; i++)
    {
        for(int j=1; j<=30; j++)
        {
            if(j==1 || j==i) dp[i][j]=1; //끝 모서리부분은 1고정
            else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }

    for(int i=R; i<R+W; i++)
    {
        for(int j=C; j<=C+i-R; j++)
        {
            result += dp[i][j]; //범위내 더해주기
        }
    }

    cout << result;

    return 0;
}

 

상당히 유명한 파스칼의 삼각형 문제를 이용한 dp 문제이다.

처음에 파스칼의 삼각형을 먼저 채워주고 시작한다.

그 이후에 문제에 주어진 범위내의 값만 따로 더해주고 출력해주면 된다.