백준 16456 - 하와와 대학생쨩 하와이로 가는 거시와요~

icpc.me/16456

 

몇가지 항에 대해 직접 손으로 경우의 수를 찾아보면

 

$f(n) = f(n - 1) + f(n - 3)$ 형태의 점화식이 성립됨을 찾을 수 있다.

 

DP를 통해 이 점화식을 풀자.

 

전체코드

#include <bits/stdc++.h>

#define mod 1000000009

using namespace std;
using ll = long long;

ll dp[50000];

int main()
{
    int n;
    cin >> n;
    
    dp[0] = dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i < n; ++i)
        dp[i] = (dp[i - 1] + dp[i - 3]) % mod;
    
    cout << dp[n - 1];
}