[15489] 파스칼 삼각형

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

15489번: 파스칼 삼각형

<문제>

행과 열, 2개의 상태로 위치가 구분되므로 2차원 dp를 생성한다.

시각적으로 보이는걸 수식으로 구체화해보면, dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] 이다.

 

정삼각형은 2중for로 구성할 수 있는데, 초기값은 각각 r과 c로, 입력받은 그대로 넣어주면 되지만

조건문의 경우 조금 더 신경써줄 부분이 존재하는데...

i가 바깥, j가 안쪽의 for문으로, 총 2중for라 할때 조건문은 아래와 같다.

i<r+w
j<c+(i-r+1) 

(i-r+1)은 곧 맨 위에서 몇번째 행인지를 의미한다.

피라미드식 별찍기를 할때 안쪽의 for는 바깥쪽의 for에 영향을 받아 작동하였는데( j<i 처럼 말이다)

항상 초기값이 1,1이었던 별찍기보다 조금 더 일반화된 형태라고 생각하면 되겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int r, c, w, dp[31][31];
int main(void) {
    cin >> r >> c >> w;
    int i, j;
    dp[1][1] = 1;
    for (i = 2; i <= 30; i++)
        for (j = 1; j <= i; j++) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    int ans = 0;
    for (i = r; i < r + w; i++)
        for (j = c; j < c + (i - r + 1); j++) ans += dp[i][j];
    cout << ans;
    return 0;
}