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

[문제]

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

16395번: 파스칼의 삼각형

 

[문제풀이]

2차원 배열을 만들어서 풀 경우에 점화식 DP[i][j] = DP[i-1][j-1] + DP[i-1][j] 로 풀 수가 있다.

j의 값이 0이거나 i와 같아질 경우에는 1이 되게 만들자.(16~19)

 

[코드]

#include<iostream>
#define endl "\n"
 
using namespace std;
 
int pascal[31][31];
 
void combine(int n,int k){
    pascal[0][0] = 1;
    pascal[1][0] = 1;
    pascal[1][1] = 1;
 
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<=k;j++){
            
            if(j == i or j == 0){
                pascal[i][j] = 1;
                continue;
            }
 
            pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
        }
    }
 
    cout<<pascal[n-1][k-1];
}
 
int main(){
    int n,k;
    cin>>n>>k;
    combine(n,k);
 
    return 0;
}