1309번: 동물원

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


$O(n)$

n행까지 배열하는데 n행에 배열 안 한 경우 가지수 dp1[n], 왼쪽에만 한 마리 배열한 경우 가지수 dp2[n] 라고하자.
dp1[0]=1 dp2[0]=0
dp1[i]=dp1[i-1]+dp2[i-1]*2
dp2[i]=dp1[i-1]+dp2[i-1]
이다.
정리해서 최적화하면
dp[0]=1 dp[1]=3
dp[n]=dp[n-1]*2+dp[n-2]
으로 쓸 수 있다.

#include<cstdio>
#define mod 9901
const int MAX_N = 1e5;
int dp[MAX_N + 1], n;
int main() {
    scanf("%d", &n);
    dp[0] = 1; dp[1] = 3;
    for (int i = 2; i <= n; i++) dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % mod;
    printf("%d", dp[n]);
    return 0;
}