[python/파이썬] 백준 15489 파스칼 삼각형

[문제 출처]

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

15489번: 파스칼 삼각형

 

[문제 풀이]

일단 파스칼의 삼각형을 필요한 만큼 만들어놓고 그다음에 문제에서 주어진 값을 계산하는 방식으로 해결한다.

2차원 리스트을 이용 하여 파스칼의 삼각형을 만든다.

 

r번째 줄에 있는 수를 꼭짓점으로 하고 한 변의 길이가 w인 삼각형이 나오려면

파스칼의 삼각형은 최소 r+w-1줄이 되어야 한다.

따라서 n = r+w-1로 두고 n*n 리스트를 선언하고 n번째 줄에 n개의 원소만 넣어준다.

각 줄의 첫번째 원소와 마지막 원소는 1이고 나머지는 위에 있는 두 원소의 합으로 이루어진다.

이를 이용하여 파스칼의 삼각형의 값들을 채우고 그 후에 r, c, w를 이용하여 값을 구한다.

 

import sys
input = sys.stdin.readline

r,c,w = map(int, input().split())

n = r + w - 1
dp = [[0] * n for _ in range(n)]

dp[0][0] = 1
for i in range(1, n):
    dp[i][0] = 1
    dp[i][i] = 1

for i in range(2, n):
    for j in range(1, i):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

result = 0
for i in range(w):
    for j in range(i+1):
        result += dp[i+r-1][c+j-1]

print(result)