[BOJ / Python] 16395 - 파스칼의 삼각형

문제 링크

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

16395번: 파스칼의 삼각형

---

풀이

• 바로 위 행의 인접한 두 수의 합을 구하기 위해 다음과 같은 형태로 배열을 만들었습니다. 파란색 삼각형 부분은 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])