[BOJ] 2225. 합분해

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 

20 2

예제 출력 1 

21

문제를 아무리 읽어도 감이 안왔다. 언제쯤 dp 문제에 감을 익힐 수 있을까 ..
질문글도 몇개 읽어봐도 모르겠어서 구글링을 계속 했다. 몇가지 해설을 봤지만 아무리 해도 이해가 안됐다. 그러다 표를 그려보신 분을 찾아서 나도 표를 그려봤다. 역시 안될때는 그림으로 이해하는게 최고인 것 같다..


점화식은 간단하다.
dp[n][k] = dp[n][k-1] + dp[n-1][k]

코드>>

#include <iostream> #define MOD 1000000000 using namespace std; long long dp[201][201]={0,}; int main(){     int N,K;     cin>>N>>K;            for(int i=1;i<=N;i++)         dp[i][1] = 1;     for(int i=1;i<=K;i++)         dp[1][i] = i;     for(int i=2;i<=N;i++){         for(int j=2;j<=K;j++){             dp[i][j] = dp[i][j-1] + dp[i-1][j];             dp[i][j] %= MOD;         }     }          cout<<dp[N][K];      } Colored by Color Scripter

cs