[Python] 백준 16395번: 파스칼의 삼각형

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

 

 

 

[풀이]

기존 연산이 다음 연산에 영향을 미치기 때문에 DP로 풀이했다.

우선 대각선 형태로 되어 있는 것을 N*N 형태의 배열로 만들었다.

 

또한, 초기값을 1로 만들고 나서 다음 연산할 부분만 2중 for문으로 만들어서 파스칼의 삼각형을 완성했다.

 

 

[코드]

n, k = map(int, input().split())
dp = [[1] * (n + 1) for _ in range(n + 1)]

for i in range(3, n + 1):
    for j in range(2, i):
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

print(dp[n][k])

 

 

 

[시간복잡도]

O(N^2)