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

16395번: 파스칼의 삼각형 (acmicpc.net)

16395번: 파스칼의 삼각형

문제코드

n,k=map(int,input().split()) #1~30
arr=[[],[1],[1,1]]
for i in range(3,n+1):
    x=[1]*i
    for j in range(1,i-1):
        x[j]=arr[i-1][j-1]+arr[i-1][j]
    arr.append(x)
print(arr[n][k-1])

 

코드해설

다이나믹프로그래밍 이용 문제. 작은 문제로 쪼개어... 각 항마다 위의 두개를 더한다 라는 작은 문제로 쪼갬.

이를 반복하여 삼각형을 만들고 답을 구함,

따로 식을 적지 않고 arr에 초반 1과 2일떄를 저장. 다음부분부턴 반복하여 한 줄씩 구한후 arr에 추가하는 방식. 바텀업방식으로 작은 것부터 모두 구함.