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

https://www.acmicpc.net/problem/16395

16395번: 파스칼의 삼각형

 

문제분석

1. 분류
   • 수학, 다이나믹 프로그래밍, 조합론
2. 문제설명
   • N번째 행에는 N개의 수가 있다.
   • 첫 번째 행은 1이다.
   • 두 번째 행부터 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다.
   • 정수 n과 k가 주어졌을 때, 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 출력한다. (1 ≤ k ≤ n ≤ 30)

 

코드

1	n, k = map(int, input().split())
2
3	pascal = [[1 for _ in range(i)] for i in range(1, 31)]    #1<=k<=n<=30
4	for i in range(2, 30):
5	for j in range(1, i):
6	pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]
7
8	print(pascal[n-1][k-1])

 

문제풀이

• n과 k는 1 이상 30 이하이므로 n=30까지 파스칼의 삼각형 모양으로 1을 채워 만들어둔다.
• 첫 번째 행은 1이므로 두 번째 행부터 파스칼의 삼각형 식대로 계산을 한다. (두 번째 행부터 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합 → pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j])
• n번째 행의 k번째 수를 출력해야 하므로 pascal[n-1][k-1]을 출력한다.