알고리즘 분류)
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]
임을 알 수 있다
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])