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

문제

접근 방법

삼각형이지만 숫자를 왼쪽 정렬하여서 보면 사각형으로 볼 수 있습니다.
5줄까지의 예시를 들어보겠습니다.

1 0 0 0 0
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1

규칙을 살펴보면 맨 좌측은 1이고 좌측에서 2번째 줄부터는 좌측 위에 존재하는 값과 위에 존재하는 값의 합인 걸 확인할 수 있습니다.

코드

#include <iostream>
using namespace std;
#define SIZE 31
int R, C, W;
long long answer;
int dp[SIZE][SIZE];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> R >> C >> W;
    --R, --C;

    for (int i = 0; i < SIZE; ++i)
    {
        dp[i][0] = 1;
    }

    for (int i = 1; i < SIZE; ++i)
    {
        for (int j = 1; j < SIZE; ++j)
        {
            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)
        {
            answer += dp[i][j];
        }
    }

    cout << answer;
    return 0;
}

풀이

점화식은 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]입니다.
점화식을 통해 미리 파스칼 삼각형을 구한 뒤 합을 구하면 됩니다.

합의 경우 폭이 1칸에서 시작하여 R칸까지 도달한다는 점을 유의하여 반복문을 작성해 주시면 됩니다.