[백준 ] 2225(파이썬) - 합분해

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

2225번: 합분해

• 이 문제를 처음 읽고 든 생각은 'dp로 풀어야겠다' 였다. 바텀업 방식을 이용해서 풀었다.
• 나는 dp는 웬만한 문제는 일단 표를 그려서 적어보고 규칙을 찾는 방법으로 푼다.
• 이 방식도 n,k 두 개의 변수로 구현하는 거니까 2차원 배열의 dp 리스트를 만들어준다.

n을 k개로 라고 생각해서 dp 테이블을 위와 같이 작성해봤다. 6,4 일 때의 dp 리스트이다.

• 위와 같이 규칙을 찾으니까 dp [i][j] = dp[i-1][j] + dp[i][j-1] 라는 점화식이 나왔고 2중 for문에 적용시켜주면 된다.

import sys
input = sys.stdin.readline


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

dp = [[0] * (n+1) for _ in range(k)]

for i in range(k):
    dp[i][0] = 1
for i in range(n+1):
    dp[0][i] = 1
for i in range(1,k):
    for j in range(1,n+1):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000000

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