Algorithm/Baekjoon

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

MaxLevel 2024. 1. 20. 19:51

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

 

16395번: 파스칼의 삼각형

파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
 
 
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];
}
 
 
 
 
 cs

 

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

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