카테고리 없음
[백준/python] 16395번: 파스칼의 삼각형
ㄱㅈㅅㅇ
2023. 9. 17. 04:56
16395번: 파스칼의 삼각형 (acmicpc.net)
16395번: 파스칼의 삼각형
파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행
www.acmicpc.net
문제코드
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에 추가하는 방식. 바텀업방식으로 작은 것부터 모두 구함.