[BOJ/C++] 2193 이친수

동적 계획법을 이용해 문제를 해결할 수 있습니다.

우선 각 자릿수에서 이친수의 개수를 알아봅시다.

N=1

1

N=2

1 0

N=3

1 0 0
1 0 1

N=4

1 0 0 0
1 0 0 1
1 0 1 0

위의 규칙들을살펴보았을 때 다음과 같은 점화식을 얻을 수 있습니다.

$DP[N] = DP[N-1] + DP[N-2]$

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static int64 DP[91] = {};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    int N;
    cin >> N;

    DP[1] = 1;
    DP[2] = 1;
    DP[3] = 2;

    for (int i = 4; i <= N; i++)
        DP[i] = DP[i - 1] + DP[i - 2];

    cout << DP[N];



    return 0;

}