2193번 : 이친수

이차원 dp로 구성한다.

dp[i][2]로 구성하는데 dp[i][0]는 i자리 이친수 중 가장 뒷자리가 0인 수를, dp[i][1]는 i자리 이친수 중 가장 뒷자리가 1인 수를 의미한다.

dp[i-1][0] 뒤에 0이 올 수 있고 dp[i-1][1] 뒤에도 0이 올 수 있다.

dp[i-1][1] 뒤에는 0만 올 수 있다.

여기서 N이 90까지이므로 long long int로 구성한다.

#include <stdio.h>

long long int dp[91][2], N; //마지막자리가 0으로 끝나는지, 1로 끝나는지 => 개수

int main() {

dp[1][0] = 0;

dp[1][1] = 1;

dp[2][0] = 1;

dp[2][1] = 0;

scanf("%d", &N);

for (int i = 3; i <= N; ++i) {

dp[i][0] = dp[i - 1][0] + dp[i - 1][1];

dp[i][1] = dp[i - 1][0];

}

printf("%lld", dp[N][0]+dp[N][1]);

}