[백준] 1, 2, 3 더하기 3
2021. 7. 14. 23:08ㆍ알고리즘 관련/DP
1, 2, 3 더하기 3 (실 2) : https://www.acmicpc.net/problem/15988
재귀문제인 1, 2, 3 더하기 문제(https://sanghoonly.tistory.com/21)를, DP를 활용하여 메모이제이션을 적용한 문제 및 코드이다.
이전 문제는 n의 범위가 작아서 단순 재귀 호출로 충분히 풀 수 있었지만, 이 문제의 경우는 n이 1000000이하로 급격하게 커지니 메모이제이션은 필수이다. 또한 n이 커짐에 따라 정답도 급격하게 증가하니, 정수 범위에 조심할 것!!
#include <iostream>
#include <memory.h>
#include <stdio.h>
using namespace std;
long long cache[1000001];
long long recur(long long n)
{
long long &ref = cache[n];
if (ref != -1)
return ref;
if (n == 0)
return 1;
long long cnt = 0;
for (long long num = 1; 3 >= num; num++)
{
if (n - num >= 0)
cnt += recur(n - num);
}
return ref = cnt % 1000000009;
}
int main(void)
{
int testCnt, N;
scanf("%d", &testCnt);
memset(cache, -1, sizeof(cache));
cache[0] = 1;
cache[1] = 1;
while (testCnt--)
{
scanf("%d", &N);
printf("%d\n", recur(N));
}
return 0;
}
'알고리즘 관련 > DP' 카테고리의 다른 글
[백준] RGB 거리 (0) | 2021.07.15 |
---|---|
[백준] 최대 증가 부분 수열(LIS) 문제 (0) | 2021.07.14 |
[백준] 제곱수의 합 (0) | 2021.07.14 |
[백준] 합분해 (0) | 2021.07.14 |
[백준] 1로 만들기 (0) | 2021.07.06 |