백준 2193 (이친수)

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

점화식 dp[i] = dp[i-1] + dp[i-2] 이용

첫 숫자는 무조건 10이다. 

10 뒤로 오는 숫자가 문제인데,

만약 1이 올 경우는, dp[i-2]와 같다.

만약 0이 올 경우는, dp[i-1]의 맨 앞 자리 숫자를 제외한 모두와 같다.

ex)

2: 10

3: 101 100

4 : 1010 1001 1000

5 : 10010 10001 10000 10101 10100

#include <iostream>
using namespace std;
 
int main(){
    long dp[91];
    int N;
    cin >> N;
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3; i <= N; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[N];
}