백준 16395 - 파스칼의 삼각형

태태·2023년 5월 18일
0

문제

알고리즘 분류)

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

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

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

1
11
121
1331
14641
15101051
1615201561

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])
profile
과정에서 재미를 느끼지 않는데 성공하는 일은 거의 없다

0개의 댓글