[BOJ/백준] 2225 합분해

# 2225번 합분해


N,K = map(int,input().split())

dp = [[1]*(N+1) if i==0 else [0]*(N+1) for i in range(K)]


for ind in range(1,K):
    for prev_num in range(N,-1,-1):
        for current_num in range(N,-1,-1):
            if prev_num + current_num <=N:
                dp[ind][prev_num+current_num] += dp[ind-1][prev_num]


print(dp[K-1][N]%1000000000)

K 번을 더햇 N이 나오는 경우이므로, DP를 (N+1)*K 형태로 만들어 놨다. 그래서 이전 행에서의 prev_num과 현재의 current_num을 더해서 N을 넘지 않는 경우 새로운 행에 그 횟수를 저장해주는 방식을 해주었다.

 

 

N,K = map(int,input().split())

dp = [[1]*(N+1) if ind==0 else [0]*(N+1) for ind in range(K)]


for k in range(1,K):
    for num in range(N+1):
        dp[k][num] = (dp[k-1][num] + dp[k][num-1])%1000000000

print(dp[K-1][N])

위의 방식대로 풀어도 시간내에 통과하지만 점화식을 구하면 좀 더 쉽게 구할 수 있다.

 

DP[K][N] = DP[K-1][N] + DP[K-1][N-1] + .... + DP[K-1][0] 이다.

DP[K][N-1] = DP[K-1][N-1] + DP[K-1][N-2] + .... + DP[K-1][0] 인 것을 알 수 있따.

 

이것을 봐보면 DP[K][N] = DP[K-1][N] + DP[K][N-1]인 것을 알 수 있다.

 

이 점화식을 통해 구하면 좀 더 쉽게 구할 수 있다.