Search

합분해

Created
2021/03/23 01:58
문제 번호
2225
카테고리
DP

Memo

x1+x2+...+xk=nx_1 + x_2 + ... + x_k = n 이 나오는 경우의 수를 구해야 하는 상황
x1x_1 에서 xkx_k중의 임의의 수 ttxtx_t라고 해보면, x1+...+xt1+xt+1+...+xk=nxtx_1 + ... + x_{t-1} + x_{t+1} + ... + x_k = n - x_t가 됨
즉, k1k - 1개의 정수를 이용하여 nxtn-x_t를 만들어 내면 되는 상황
... 반복을 통해 점화식 유도 가능...
이 때 고려할 수 있는 것은 ttx1x_1에서 xkx_k중 어떤 수도 가능하므로 모든 경우에 대해서 더하면 됨
우선 다음과 같은 선행 조건을 찾을 수 있었음
1.
0개의 정수를 이용하여 nn을 만드는 경우는 오로지 0개의 경우만 존재
2.
1개의 정수를 이용하여 nn을 만드는 경우는 오로지 1개의 경우만 존재
3.
kk개의 정수를 이용하여 0을 만드는 경우는 오로지 1개의 경우만 존재
→ 테이블을 만들 수 있음
Search
Memoization
K/N
0
1
2
3
4
1
1
1
1
1
1
2
3
4
5
COUNT7
위 점화식에 따르면 K=2,N=1K = 2, N = 1에 대해서는 K=1,N=0K = 1, N = 0, K=1,N=1K = 1, N = 1을 더한 것과 같은 의미
K=2,N=2K = 2, N = 2에 대해서는 K=1,N=0K = 1, N = 0, K=1,N=1K = 1, N = 1, K=1,N=2K = 1, N = 2를 더한 것과 같음
... 반복 ...
이렇게 되면 i, j를 두어 기본적으로 K와 N에 대해서 처리를 하고, k를 두어 내부적으로 자기 자신 j까지 더하도록 만드는 삼중 루프로 푸는 것이 가능
규칙?
K,NK, N이 주어졌을 때 Memoization을 구하기 위해서 K1K - 1번째의 NN까지의 모든 합을 구하기 위해 루프를 굴리지 않더라도 이를 구하는 것이 가능
K1K -1번째의 N1N- 1까지의 합은 K,N1K, N - 1에 해당하는 Memoization에 해당
→ 여기에 K1,NK - 1, N에 해당하는 Memoization을 더하면 됨
→ 즉, K,NK, N에 대한 Memoization은 좌측 값 + 상단 값을 통해 구할 수 있음

Code

제출 날짜

@2/17/2021

메모리

2280 KB

시간

0 ms
#include <iostream> #include <vector> int g_n; int g_k; std::vector<std::vector<int>> g_memoi; void pre_setting(void) { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } void input_action(void) { std::cin >> g_n >> g_k; g_memoi = std::vector<std::vector<int>>(g_k + 1, std::vector<int>(g_n + 1, 0)); for (int i = 0; i <= g_n; i++) g_memoi[1][i] = 1; for (int i = 0; i <= g_k; i++) g_memoi[i][0] = 1; } void logic(void) { for (int i = 2; i <= g_k; i++) for (int j = 1; j <= g_n; j++) g_memoi[i][j] = (g_memoi[i - 1][j] + g_memoi[i][j - 1]) % 1000000000; } void output_action(void) { std::cout << g_memoi[g_k][g_n]; } void solution(void) { input_action(); logic(); output_action(); } int main(void) { pre_setting(); solution(); return (0); }
C++