[Algorithm]Baekjoon 16395번 :: 파스칼의 삼각형

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

16395번: 파스칼의 삼각형

 
 
 
int n, k;
int pascalTriangle[31][31] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> k;
 
    pascalTriangle[1][1] = 1;
 
    for (int i = 2; i <= n; ++i)
    {
        pascalTriangle[i][1] = pascalTriangle[i][i] = 1;
 
        for (int j = 2; j <= i; ++j)
        {
            pascalTriangle[i][j] = pascalTriangle[i - 1][j - 1] + pascalTriangle[i - 1][j];
        }
    }
    
    cout << pascalTriangle[n][k];
}
 
 
 
 

 

일정한 규칙이 있는 형태의 삼각형이다.

pascalTriangle[i][j] = pascalTriangle[i-1][j-1] + pascalTriangle[i-1][j] 가 성립되기 때문에, n * n번의 시간복잡도로 수행할 수 있다.