백준 2225 합분해 C++

합분해 문제 바로가기

https://yabmoons.tistory.com/128
해당 블로그 글을 보고 문제를 풀었습니다.

이번 문제는 합분해 문제입니다.
만약 N,K가 3,3이라면 3가지 숫자를 가지고 3을 만들어야합니다.
여기서 어떤 알고리즘을 적용할까 했는데, 모듈러 연산을 보고 경우의 수가 너무 많다고 생각했습니다.
각 자리마다 0부터 시작해서 문제를 재귀로 풀어볼까 생각했는데
경우의 수가 너무 많은거같아, 알고리즘을 보았지만 DP라고 했는데 이조차도 DP를 어떻게 적용해야할지 감이 안잡혀서 답을 봤습니다.

일단 N,K가 3,3일때의 경우를 전부 적어보겠습니다.
003
012 102
021 201 111
030 120 210 300
이렇게 10개 입니다.

그렇다면, DP를 어떻게 적용해야할까 생각했는데, 약간의 아이디어를 2293 동전 C++문제에서 가져왔습니다.
문제 바로가기
약간의 설명을 하자면 만약에, 2원을 만들수있는 경우가 3가지라고 가정해보겠습니다. 그러면 3원을 가지고 5원을 만들 수 있는 경우는 몇가지일까요? 바로 3가지입니다.

왜냐하면, 2원+3원은 5원입니다. 그런데 2원을 만들수있는 경우가 3가지이면, 각 3가지 방식에 3원만 넣으면 되는것이기 때문입니다.
DP[5]+=DP[5-3]

이처럼, DP는 이전의 내용을 가져와서 더해줘야합니다.
그러면 해당문제에서는 어떤 이전의 내용을 가져와야할까요?

2개를 가지고 0을 만드는 방법을 생각해봅시다.
여기다가 그냥 3을 더하면 3가지숫자로 3을 만드는것일겁니다.

2개를 가지고 1을 만드는 방법을 생각해봅시다.
여기다가 그냥 2을 더하면 3가지숫자로 3을 만드는것일겁니다.

2개를 가지고 2를 만드는 방법을 생각해봅시다.
여기다가 그냥 1을 더하면 3가지숫자로 3을 만드는것일겁니다.

2개를 가지고 3을 만드는 방법을 생각해봅시다.
여기다가 그냥 0을 더하면 3가지숫자로 3을 만드는것일겁니다.

이처럼
//앞이 사용하는 숫자 갯수, 뒤가 만들려는 숫자
DP`[3][3]' = DP[2][0]+DP[2][1]+DP[2][2]+DP[2][3]입니다.
003 -> 두개의 숫자로 0을 만드는경우
012 102 -> 두개의 숫자로 1을 만드는경우
021 201 111 -> 2를 만든느경우
030 120 210 300 -> 3을 만드는경우

for (int i = 0; i <= N; i++) {
		DP[1][i] = 1;
	}

처음에는 어차피 숫자1개로 N을 만드는 방법은 그냥 N을 쓰는수밖에 없습니다.
즉 이 경우는 숫자 1개를 가지고 N을 만드는방법입니다.

//2개를 가지고
	for (int k = 2; k <= K; k++) {
		//0을만드는법,1을 만드는법,,,N을 만드는법
		for (int n = 0; n <= N; n++) {
			//DP[3][3] = DP[2][0] + DP[2][1]... DP[2][3];
			for (int i = 0; i <= n; i++) {
				DP[k][n] += DP[k - 1][i];
			}
			DP[k][n] = DP[k][n] % 1000000000;
		}
	}

첫번째 for문: 숫자 2개를 가지고 K개까지 확인한다.
두번째 for문: 숫자 N까지 만드는방법
세번째 for문: DP`[3][3]' = DP[2][0]+DP[2][1]+DP[2][2]+DP[2][3]이 로직을 구현

정답코드

#include <iostream>

using namespace std;

long long DP[201][201];

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

	for (int i = 0; i <= N; i++) {
		DP[1][i] = 1;
	}

	//2개를 가지고
	for (int k = 2; k <= K; k++) {
		//0을만드는법,1을 만드는법,,,N을 만드는법
		for (int n = 0; n <= N; n++) {
			//DP[3][3] = DP[2][0] + DP[2][1]... DP[2][3];
			for (int i = 0; i <= n; i++) {
				DP[k][n] += DP[k - 1][i];
			}
			DP[k][n] = DP[k][n] % 1000000000;
		}
	}

	cout << DP[K][N] << "\n";
	return 0;
}