[백준] 2225: 합분해 (Python)

문제📖

풀이🙏

• dp[k][n]으로 2차원 dp테이블을 생성한다.
• k가 1, 2, 3 일때 n의 값을 만들 수 있을 때 간단히 정리하면 다음과 같다.
  
• 다음을 통해 dp[i][j]는 테이블의 왼쪽과 위에서 더한 값
  즉, dp[i][j]=(dp[i][j-1]+dp[i-1][j])이라는 점화식을 구할 수 있다.

코드💻

n, k = map(int,input().split())
dp = [[0] * 201 for i in range(201)]

for i in range(1, 201):
    dp[1][i] = 1
    dp[2][i] = i+1

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

print(dp[k][n])