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])