[백준] 2225 합분해 파이썬 python

문제링크

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

2225번: 합분해

 

코드

import sys
 
input = sys.stdin.readline
 
n,k = map(int,input().split())
mod = 1000000000
d=[[0]*(k+1) for _ in range(n+1)]
 
for i in range(n+1):
    for j in range(1,k+1):
        if i==0:
            d[i][j]=1
        else:
            d[i][j] = (d[i-1][j]+d[i][j-1])%mod
print(d[-1][-1])

 

 

POINT

- DP로 접근

- d[i][j] : i를 만드는데 j개 숫자 사용했을 때 경우의 수

ex) d[2][3] : 2를 만드는데 3개의 숫자 사용 = d[0][2]+d[1][2]+d[2][2]

{0을 만드는 데 숫자 2개 사용한 case(0+2=2)} + {1을 만드는 데 숫자 2개 사용한 case(1+1=2)} +
{1을 만드는 데 숫자 2개 사용한 case(2+0=2)}

다음 표와 따라, d[n][k] = d[n-1][k] + d[n][k-1] 공식을 찾을 수 있다!