Memo
이 나오는 경우의 수를 구해야 하는 상황
에서 중의 임의의 수 를 라고 해보면, 가 됨
즉, 개의 정수를 이용하여 를 만들어 내면 되는 상황
... 반복을 통해 점화식 유도 가능...
이 때 고려할 수 있는 것은 는 에서 중 어떤 수도 가능하므로 모든 경우에 대해서 더하면 됨
우선 다음과 같은 선행 조건을 찾을 수 있었음
1.
0개의 정수를 이용하여 을 만드는 경우는 오로지 0개의 경우만 존재
2.
1개의 정수를 이용하여 을 만드는 경우는 오로지 1개의 경우만 존재
3.
개의 정수를 이용하여 0을 만드는 경우는 오로지 1개의 경우만 존재
→ 테이블을 만들 수 있음
Search
위 점화식에 따르면 에 대해서는 , 을 더한 것과 같은 의미
에 대해서는 , , 를 더한 것과 같음
... 반복 ...
이렇게 되면 i, j를 두어 기본적으로 K와 N에 대해서 처리를 하고, k를 두어 내부적으로 자기 자신 j까지 더하도록 만드는 삼중 루프로 푸는 것이 가능
규칙?
이 주어졌을 때 Memoization을 구하기 위해서 번째의 까지의 모든 합을 구하기 위해 루프를 굴리지 않더라도 이를 구하는 것이 가능
→ 번째의 까지의 합은 에 해당하는 Memoization에 해당
→ 여기에 에 해당하는 Memoization을 더하면 됨
→ 즉, 에 대한 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++
복사