B - トリボナッチ数列 / AtCoderBeginnerContest #006

abc006.contest.atcoder.jp

#include <iostream>
using namespace std;

#define MAX_N 1000000
#define MOD 10007

int a[MAX_N];

void Solve(int n)	{
	a[0]=a[1]=0;
	a[2]=1;
	for (int i=3; i<=n; ++i)
		a[i]=(a[i-3]+a[i-2]+a[i-1])%MOD;
	cout << a[n-1] << endl;
}

int main(void)	{
	int n;

	cin >> n;
	Solve(n);
	return 0;
}

動的計画法を使用、第n項までの答えを事前に列挙し最後に第n項を出力。
～了～