백준 2225 / CPP

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

이 문제의 경우 점화식을 세우기 빡셌다 이문제의 경우 일단 대충의 로직은

이 상태에서 시작하게 된다 맨위에 파란부분은 수고 그이후의 행들은 해당 숫자를 만드는 데 사용하는 수의 개수를 의미합니다 현재 1행에 숫자 1들이 들어간 이유는 각 수를 만드는데는 자기자신 하나만 필요하기 때문입니다.

 

자 그리고 다음 행을 봅시다
0을 만드는데는 어차피 0 하나로 밖에 못만드니 

이렇게 채워 줍시다
그다음 2행을 채우게 되면 숫자 2개로 해당 수를 만드는 방법을 봅시다 1은 1+0 과 0+1 로만들 수 있습니다 2는 1+1과 0+2와  2+0으로 만들 수있습니다 우리는 여기서 알수있는게 해당행의 이전행에서의 나자신까지의 합을 모두 더해주면 된다는 것을 알수 있습니다. 0을 선택하게 되면 자동을 2가선택 1을 선택하면 자동으로 1이선택 2를 선택하면 자동으로 0이선택되니 이전행의 자신 열까지의 합을 넣어주면 됩니다

그후 3행은 숫자 3개를 이용하는 것이기에 이전 행에서 2개를 선택한 로직에서 추가로 확장하면 됩니다 숫자 3개로 1을 만드는 방법은 (0+0)+1 , (1+0)+0,  (0+1)+0 이고 2의경우는 이전에 2개를 선택한거에 추가로 해당 수를 제외한 수를 더해주면 자동으로 더해지게 됨으로 이전행의 열들의 값을 더해주면 됩니다

결과적으로 그림이 이렇게 되서 완료가 됩니다.
해당 코드를 구현하면

#include <iostream>
using namespace std;
long long m = 1000000000;
long long dp[204][204];
int main() {
	long long n, k;
	cin >> n >> k;

	for (int i = 0; i <= n; i++) {
		dp[1][i] = 1;
	}


	for (int i = 2; i <= k; i++) {
		for (int j = 0; j <= n; j++) {
			for (int z = 0; z <= j; z++) {
				dp[i][j] += dp[i - 1][z];
			}
			dp[i][j] %= m;
		}
	}
	cout << dp[k][n];
}