Koala - 5기/코딩테스트 준비 스터디
[BOJ / Python] 16395 - 파스칼의 삼각형
IT Act.
2022. 1. 23. 22:11
문제 링크
https://www.acmicpc.net/problem/16395
16395번: 파스칼의 삼각형
파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행
www.acmicpc.net
풀이
- 바로 위 행의 인접한 두 수의 합을 구하기 위해 다음과 같은 형태로 배열을 만들었습니다. 파란색 삼각형 부분은 n 이 5일때 나오는 형태입니다.
- [n+1][n+1] 크기만큼의 배열을 선언하고 0으로 초기화합니다.
- (1,1) 위치의 값을 1로 초기화하면 세번째 행부터 모든 값은 바로 위 행의 인접한 두 수의 합으로 구할 수 있습니다.
- 세번째 행은 배열에서는 2에 해당하므로 첫번째 반복문은 반복문은 2부터 n+1까지 실행합니다.
- 두번째 반복문은 1열부터 i+1열까지 돌면서 dp[i-1][j-1] + dp[i-1][j] 값을 계산해 dp[i][j]에 저장합니다.
코드
n, k = map(int, input().split())
dp = [[0]* (n+1) for _ in range(n+1)]
dp[1][1] = 1
for i in range(2, n+1):
for j in range(1, i+1):
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
print(dp[n][k])