백준 파이썬 2225 합분해

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

2225번: 합분해

 

초반에는 문제를 제대로 안읽고 itertools 툴을 사용할려했지만 한 개의 수를 여러 번 사용할 수 있으며

1000000000로 나눠야 하기 떄문에 dp라는걸 알아채는데 시간이 조금 걸렸다.

 

0~4까지 조금씩 손으로

 

규칙을 찾기위해서 조금 손으로 풀어봤는데

 

ex dp[2][2] = 6 인데 dp[2][1] + dp[1][2]를 합친 수와 같은걸 알 수 있었고

dp[3][2] 도 같은 규칙으로 이루어져 있는걸 알 수 있었다.

그리고 시간 복잡도가 가장 오래걸리는 200, 200으로 실험해 보았고 시간이 오래 걸리지 않는것을 확인.

그대로 제출 하니 정답이었다.

 

dp중에서도 좀 쉬운 문제였고 골드까지?? 받을 문제였나 싶었다.

 

n,k = map(int,input().split())

dp=[[1]*(n+1)]

for i in range(1,k):
    dp.append([0]*(n+1))
    dp[i][0] = 1
    for j in range(1,n+1):
        dp[i][j]=dp[i-1][j] + dp[i][j-1]

print(dp[k-1][n]%1000000000)