백준 16395 - 파스칼의 삼각형

문제

알고리즘 분류)

• 수학
• 다이나믹 프로그래밍
• 조합론

---

dp를 이용하여 푸는 문제중 쉬운편의 문제이다
일단은 문제를 풀기위하여 삼각형에 알맞은 2차원 배열을 생성하였다

DP의 핵심은 점화식 구성인데 이 문제의 삼각형의 점화식은

1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1
1	6	15	20	15	6	1

array[i][j] = array[i-1][j-1] + array[i-1][j]
임을 알 수 있다

---

소스코드

python)

N,K = map(int, input().split())
array = []
for i in range(1,N+1):
    array.append([1]*i)
    
for i in range(2,N):
    for j in range(1,i):
        array[i][j] = array[i-1][j-1] + array[i-1][j]
        
print(array[N-1][K-1])