백준 2193번 : 이친수 (C 언어)

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

2193번: 이친수

Code:

#include <stdio.h>
 
long long dp[91][2];
 
int main() {
    int N;
    scanf("%d", &N);
 
    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("%lld\n", dp[N][0] + dp[N][1]);
 
    return 0;
}
 

문제풀이:

이 문제는 dynamic programming (DP)를 사용하여 풀 수 있습니다. 문제의 조건에 따르면, N자리 이친수는 N-1 자리 이친수에 '0'을 추가하거나 N-2 자리 이친수에 '01'을 추가하는 경우로 나눌 수 있습니다.