https://www.acmicpc.net/problem/2225
2225번: 합분해첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net
살짝 꼬아서 낸 dp문제 원리는 오르막수와 같음
dp[i][j]는 i개의 정수를 더해서 j가 되는 경우의 수로 정의한다.
먼져, 직관적으로 0은 제외히고
모든 dp[1][j]와 dp[i][0]는 모두 1이라는걸 알 수 있다. (한가지경우박에 없음)
3,5를 예로 들면,
dp[3][5]는 3개를 더해서 5가 되는 경우의 수이다.
이는 dp[2][0] (마지막에 5를 더하는 경우)
dp[2][1](마지막에 5-1을 더하는 경우)
dp[2][2](마지막에 5-2를 더하는 경우)
dp[2][3](마지막에 5-3을더하는 경우)
dp[2][4])마지막에 5-4를 더하는 경우)
dp[2][5](마지막에 5-5를 더하는 경우)
의 합이라고 볼 수 있다.
이를 점화식으로 쓰면
dp[i][j]=dp[i-1][0]+dp[i-1][1]…… dp[i-1][j-1]+dp[i-1][j] 를 만들 수 있다.
%%오르막 수와 같이
dp[i-1][0]+dp[i-1][1]…… dp[i-1][j-1]를 dp[i][j-1]로 치환할 수 있으므로
dp[i][j]=dp[i-1][j]+dp[i][j-1] 로 간단하게 만들 수 있다.%%
n,k=map(int,input().split())dp=[[0]*(n+1) for _ in range(k+1)]dp[1]=[1]*(n+1)
for i in range(2,k+1): for j in range(n+1): if j==0:
dp[i][j]=1 continue
dp[i][j]=dp[i-1][j]%1000000000+dp[i][j-1]%1000000000
print(dp[k][n]%1000000000)