16456번: 하와와 대학생쨩 하와이로 가는 거시와요~
Baekjoon Online Judge스타트링크 (Startlink)

해당 문제는 간단한 다이나믹 문제입니다.

우선 이 문제는 문제에서 제시한 조건을 잘 분석해야 합니다.

문제의 조건을 보면

1.어떤 섬을 보고 바로 그 다음 섬으로 갈 수 있사와요...
2. 어떤 섬을 보고 한 섬을 건너뛰고 그 다음 섬으로 갈 수도 있사와요...
3. 어떤 섬을 보고 그 이전 섬으로 갈 수 있사와요...

이렇게 세가지가 있는데

조건을 보게되면 우리가 n번째 섬을 가기위해서는 n-1번째 섬에서와 n-3번째 섬에서 올수가 있다.

그러면 조건은 g[i-1]+g[i-3]의 형태를 가지게 되는데 숫자가 커질 수 있으니 1000000009으로 나누어달라고 문제에서 말을 한 바가 있기에  
g[i]=(g[i-1]+g[i-3])%1000000009 를 하면 조건이 완성되는 것이다.

#include <stdio.h>
const int div=1000000009;
long long g[50000];
int main()
{
    int n,i;
    scanf("%d",&n);
    g[0]=1,g[1]=1;
    g[2]=2;
    for (i=3;i<n;i++)
        g[i]=(g[i-1]+g[i-3])%div;
    printf("%d",g[n-1]);
}