BOJ 16456 하와와 대학생쨩 하와이로 가는 거시와요~

하와와 대학생쨩 하와이로 가는 거시와요~
(http://boj.kr/16456)

언뜻 보면 주어진 3가지 동작으로 바로 탐색을 할 수 있을 것 같지만, 한 칸 전으로 돌아가는 동작때문에 처리하기가 힘들다.
이 전으로 돌아가는 동작만 잘 처리하면 dp식을 찾을 수 있다.

일단 한 칸 전으로 돌아가려면 돌아갈 칸은 방문한 적이 없어야 하기 때문에 무조건 2칸 이동한 후에 1칸 돌아오는 이동이 묶일 수 밖에 없다.
마찬가지로 한 칸 전으로 돌아갔으면 현재 칸, 다음 칸은 이미 방문했기 때문에 2칸을 이동할 수 밖에 없다.
즉, (+2) -> (-1) -> (+2) 는 하나의 이동이라고 볼 수 있다.

그러면 이제 식을 세우는 일은 간단하다.
$D_i$를 $i$번째 섬까지 모두 방문하는 경우의 수라고 한다.
기본적으로 $D_1=D_2=D_3=1$이고,
한 칸 전에서 (+1)로 오는 경우와 3칸 전에서 (+2) -> (-1) -> (+2)로 오는 경우 두 가지가 있으니,
$D_i=D_{i-1}+D_{i-3}(i\ge 4)$이다.

하지만 답이 $D_n$이 아니라는 점을 주의해야 한다.
위 방법으로 구한 답은 $i$번째 섬을 방문하기 전에 $i-1$개의 섬들을 모두 방문한 경우다.
하지만 마지막에 $n$번째 섬을 방문한 후 $n-1$번째 섬을 방문하는 경우도 있으니,
답은 $i\le 2$일땐 $1$, $i\ge 3$일땐 $D_n+D_{n-2}$이다.

#include <bits/stdc++.h>
 
const long long r = 1e9 + 9;
 
long long d[50001];
 
int main() {
    int n;
    scanf("%d", &n);
    
    d[1] = d[2] = d[3] = 1;
    for (int i = 4;i <= n;++i)
        d[i] = (d[i - 1] + d[i - 3]) % r;
 
    printf("%lld", n >= 2 ? (d[n] + d[n - 2]) % r : d[n]);
 
    return 0;
}