[BOJ/백준 2225/C++] 합분해

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

2225번: 합분해

[문제 요약]
- 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하여라
- 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
- 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

[문제 조건]
- 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
- 시간 제한 : 2초
- 메모리 제한 : 128MB

[문제 풀이]
문제를 잘 읽어보면 N이라는 수를 범위가 0 ≤ M ≤ N 에 해당하는 M을 K를 써서 만들면 된다.

예를 들어 입력이 (6,2)의 경우 0+6, 1+5 , 2+4 등등 다양한 경우의 수가 있다.

문제에서 엄청 큰 수로 나머지를 출력하라는거 보면 경우의 수가 엄청 많다는건데 그래서 처음에 DP로 접근을해봤다.

DP[i][j] = i라는 수를 j개의 숫자를 써서 나타낼 수 있는 경우 이렇게 정의를 하고 처음에 일단 무지성으로 한번 표를 채워보았다.

세로를 i 값 , 가로를 j 값이라 하고 초기값을 한번 설정해봤다.

dp[i][0]들은 처음에 0으로 세팅하고, dp[i][1]들은 어차피 1개의 수를 써서 i값을 만드는 경우는 i 하나 밖에 없기 때문에 1일 것이고, dp[0][i] 들은 범위가 0 ≤ M ≤ 0 이기 때문에 1가지 경우 밖에 없다.

나머지 칸들은 그냥 직접 구해서 넣어 보고 생각해봤다.

근데 자세히보면 dp[i][j] = dp[i-1][j] + dp[i][j-1]의 값을 가지는 것을 볼 수 있다.

뭐...물론 답은 어떨결에 맞긴 했는데 왜 저런 값이 나오는지 생각해보자.

어떤 수를 N을 표현하려면 위 그림과 같이 표현 할 수 있을 것이다.

이때 K-1개의 수의 합이 N-1이고 M이 1인경우 , K-1개의 수의 합이 N-2이고 M이 2인 경우... 를 모두 다 더하면 K를 이용해 N이 되는 경우다. 이것을 표에 한번 나타내면

초록색 칸의 값은 파란색 값을 모두 더한 값이 된다.

이때 바로 위의 그림에서 파란색칸의 합은 노란색칸을 의미 한다.

따라서 사실상 초록색 칸의 값은 노란색 칸 + 초록색 바로 위의 4를 더한 값과 같은 것이다.

DP[i][j] = DP[i-1][j] + DP[i][j-1]이 된다.

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>
#define pii pair<int,int>
#define MOD 1000000000
using namespace std;

int N, K;
vector<vector<unsigned long long>> dp;

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

	cin >> N >> K;
	dp.resize(N+1);
	for (int i = 0; i <= N; i++)dp[i].resize(K+1);

	for (int i = 0; i <= N; i++)
	{
		for (int j = 0; j <= K; j++)
		{
			if (i == 0) { dp[i][j] = 1; continue; }
			if (j == 0) { dp[i][j] = 0; continue; }

			dp[i][j] = (dp[i - 1][j] % MOD + dp[i][j - 1] % MOD) % MOD;
		}
	}
	cout << dp[N][K];
}

굳