[Python] 백준 #15489- 파스칼 삼각형

문제

---

15489번: 파스칼 삼각형

코드

---

My answer

import sys
input=sys.stdin.readline

r,c,w=map(int,input().split())
dp=[]
res=0
for i in range(r+w+1):
    dp.append([0]*(i+1))
    
for i in range(r+w+1):
    for j in range(i+1):
        if(j==0 or j==i):
            dp[i][j]=1
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
            
for i in range(r-1,r+w-1):
    for j in range(c-1,c-1+i-r+2):
        res+=dp[i][j]
print(res)

Another answer

import math
r,c,w=map(int,input().split())
sum=0
for i in range(r,r+w):
    for j in range(c,c+i-r+1):
        sum+=math.comb(i-1,j-1)
print(sum)

풀이

---

나는 dp를 통해서 우선 파스칼 삼각형 전체를 만들고 이후에 해당 조건에 맞는 일부분의 값을 게산하였다. 아래 코드는 파스칼 삼각형을 잘 안다면 보일텐데 파스칼 삼각형의 각항은 모두 조합의 값이다. 저 식에 있는데로 예를 들어 세번째쭐 두번째 값은 2C1이 된다. 이렇게 조합을 이용한 풀이도 있다.

파스칼삼각형