[백준 2193] 이친수

1. 점화식

 

0으로 시작이 안되므로

dp[1][0] = 0

dp[1][1] = 1

 

이후 i가 2이상부터는

dp[i-1][0] -> dp[i][0]

dp[i-1][0] -> dp[i][1]

dp[i-1][1] -> dp[i][0]

dp[i-1][1] -> dp[i][1]  (11이 연속되면 안되므로)

 

2. 코드

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);

    unsigned long long dp[91][2] = {};

    dp[1][0] = 0;
    dp[1][1] = 1;

    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
        dp[i][1] = dp[i - 1][0];
    }

    printf("%llu", dp[n][0] + dp[n][1]);

    return 0;
}