Baekjoon2225-합분해

백준 사이트 2225 - 합분해 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
비슷한 문제가 꽤나 많고, 규칙만 찾으면 어렵지 않습니다.
백준에서는 Gold5의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 공책에 먼저 그려보았습니다. n과 k가 다를 때라는 2차원 테이블을 만들었습니다.
• 먼저 k가 1일때 는 모두 1이라는 사실을 알았습니다. (숫자 1개로 N을 1개만 만들 수 있음)
  • 초기화할 때 k가 1일경우 모두 1을 넣었습니다.
• n이 입력으로 0이 들어오진 않지만 0일 때도 생각해줬습니다. 이유는 (2 + 0 + 0)이런식으로 2를 3가지 숫자로 만들 수 있어서
• 그려보니 점화식을 찾았습니다. 4가지수 (k=4)로 4를 만드는 경우의 수를 예시로 들겠습니다.(n=4)

위의 점화식 대로 프로그램을 작성한 dp예 (dp[1][~])부분 부터 출력이라 dp[0][~]이 1이라고 생각하고 보시면 됩니다.

---

5. code

#include<iostream>

const int mok = 1000000000;
const int MAX = 201;

using namespace std;

int dp[MAX][MAX] = { 0, };
int n, k;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;
	for (int i = 0; i <= k; ++i)
		dp[0][i] = 1;
	for (int i = 0; i <= n; ++i)
		dp[i][1] = 1;
	for (int i = 0; i <= n; ++i)
		dp[i][2] = i + 1;


	for (int i = 1; i <= n; ++i)
	{
		for (int j = 3; j <= k; ++j)
		{
			for (int r = 0; r <= i; ++r)
			{
				dp[i][j] += dp[r][j-1];
				dp[i][j] %= mok;
			}
		}
	}
	
	cout << dp[n][k];


}

---

6. 후기

1차원으로 푼 사람들도 많네요.