[C++] 백준 2225 합분해

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
	int N = 0;
	int K = 0;
	cin >> N >> K;

	vector<vector<int>> lists(N, vector<int>(K, 1));

	for (int i = 1; i < K; i++)
	{
		lists[0][i] += lists[0][i - 1];
	}

	for (int i = 1; i < N; i++)
	{
		for (int j = 1; j < K; j++)
		{
			lists[i][j] = (lists[i][j - 1] + lists[i - 1][j]) % 1000000000;
		}
	}

	cout << lists[N - 1][K - 1];

	return 0;
}

 

느낀점

답을 모두 list로 나열해보자

지금까지 풀었던 dp 문제들을 생각해보니 과정을 점화식으로 만들기보다 답에서 패턴을 읽어서 점화식을 만들어 나가는 것같다. 다음에 풀때는 답을 먼저 만들고 패턴을 찾아봐야겠다.

 

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