[백준][2193번][DP] 이친수

이친수

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

<소스>

#include <stdio.h>
 
int main(void){
 
    long long int N;
    long long int Dp[95][2] = {};
    scanf("%lld", &N);
    Dp[1][0] = 1;
    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][1]);
 
    return 0;
}

<문제 푼 요령>

1. 이 문제는 앞에 첫 자리 숫자가 1이 꼭 나와야 한다. 하지만 여기서 0이 앞으로 나오는 경우도 카운트 해줘야 한다.

2. 그렇기에 현재 1이 앞으로 나오는 경우에 이전 자릿수에 앞에 0이 나오는 경우의 수랑 같다.

3. 현재 0이 앞으로 나오는 경우는 이전  자릿수에 앞에 0, 1 이 나오는 경우의 합과 같다. 

4. 즉 이 규칙을 이용하여서 진행하면 DP[N][1] 에 원하는 답을 구 할 수 있다.