백준 15988번: 1, 2, 3 더하기 3 (C++)

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

 

 

풀이

DP 문제 유형 까먹을 것 같아서 오랜만에 풀어봤다.

매번 하던 재귀 방식으로 구현 했다.

 

우선, cache 배열을 만들어서 ret 으로 참조하도록 했고, N == 0 이 될 때까지 1, 2, 3을 뺀 케이스를 재귀로 호출과 함께 ret 에 더해주었다.

 

사실 나도 반복학습으로 배운 방법이라 설명이 어렵다.

 

전체 코드

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

const int MOD = 1000000009;
int N, T;
long long cache[1000001];

long long dp(long long idx) {
	if (idx == 0) return 1;
	if (idx < 0) return 0;

	long long& ret = cache[idx];
	if (ret != -1) return ret % MOD;
	ret = 0;

	ret = dp(idx - 1) + dp(idx - 2) + dp(idx - 3);

	return ret %= MOD;
}


int main() {
	cin >> T;
	memset(cache, -1, sizeof(cache));

	while (T--) {
		cin >> N;
		cout << dp(N) % MOD << '\n';
	}

}