[백준] 1, 2, 3 더하기 3

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;
}