[알고리즘] 백준 15489번: 파스칼 삼각형 (C++)

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

15489번: 파스칼 삼각형

파스칼 삼각형의 이항 계수의 특성상 r번째 행, c번째 열은 (r - 1)C(c - 1)과 같음을 이용하여 풀면 된다.

그리고, 이중 for문을 이용하여 변 w 길이를 만족하게끔 최종합에다가 (r - 1)C(c - 1)을 더해주면 된다.

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX 30 + 1
using namespace std;

int cache[MAX][MAX];

int combi(int n, int r){
    if(n == r || r == 0){
        return 1;
    }
    else{
        if(cache[n][r]){
            return cache[n][r];
        }
        else{
            return cache[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
        }
    }
}

int main(){
    int r, c, w;
    cin >> r >> c >> w;
    int sum = 0;
    int cnt = c - 1;
    
    for(int i = r - 1; i < r - 1 + w; i++){
        for(int j = c - 1; j <= cnt; j++){
            //cout << i << ' ' << j << '\n';
            sum += combi(i, j);
        }
        cnt++;
    }
    
    cout << sum;
    return 0;
}