이친수 / 2193 백준

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    //Input
    int n;
    cin >> n;
    vector<long long int> DP(n + 1, 0);
    //Main Logic Start
    //N자리의 이친수의 개수
    //Bit만 활용해야한다..(long long 범위를 초과) 
    //무조건 10으로 시작
    //N-1 자리수의 모든 가능성을 카운트
    // 1 | 0
    // 01 ; 00 | 11 ; 10 

    DP[1] = 1;
    DP[2] = 1;
    for (int i = 3; i <= n; ++i)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
    }
    //Output
    cout << DP[n];
}