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

유형: dp

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

15489번: 파스칼 삼각형

 

풀이

길이가 30까지인 파스칼의 삼각형을 미리 계산해둔 후, 입력값의 크기만큼 해당 값을 더해주면 된다.

입력값에서 r, c는 인덱스 크기에 맞춰 -=1을 해줘야 한다. (인덱스는 0부터 시작하기에)

세로의 크기는 r-1이상 r+w미만, 가로의 크기는 c-1이상 c+width미만이다.

width의 크기는 첫번째 for문에서 한번씩 +=1을 해주면 된다.

#include "vector"
#include "iostream"

using namespace std;
using ll = long long;

int main(){

    vector<vector<int>> pascal(30);

    // init pascal
    for(int i = 0; i < pascal.size(); i++){
        for(int j = 0; j < i+1; j++) pascal[i].push_back(1);
    }

    // calc pascal
    for(int i = 0; i < pascal.size(); i++){
        for(int j = 0; j < pascal[i].size(); j++){
            int idx = i-1, left = j-1, right = j;
            // 조건에 맞다면 갱신
            if(idx >= 0 && left >= 0 && right < pascal[idx].size()){
                pascal[i][j] = pascal[idx][left] + pascal[idx][right];
            }
        }
    }

    // 삼각형 길이 입력
    int r, c, w; cin >> r >> c >> w;
    r--; c--;
    int width = 0;
    ll answer = 0;

    // 계산
    for(int i = r; i < r+w; i++){
        width += 1;
        for(int j = c; j < c+width; j++) {
            answer += pascal[i][j];
        }
    }

    cout << answer << endl;

    return 0;
}