[백준 c++] 2193 이친수

문제

https://www.acmicpc.net/problem/2193
N자리 이친수의 개수를 구하는 문제다.

이친수는 다음과 같은 조건의 수다.

• 1과 0으로 이루어져있다.
• 0으로 시작하지 않는다.
• 1이 두 번 연속으로 나타나지 않는다.

풀이

N이 최대 90이기 때문에 전체 탐색을 하면 O(2^90) 으로 시간초과가 난다.
따라서 top-down 방식의 DP를 이용해서 풀었다.

long long go(int lv, int num)
lv: 트리의 레벨
num: 0 또는 1

⭐️ 출력 자료형 확인하기!!!!

코드

#include <iostream>
using namespace std;
long long n, dp[91][2];

long long go(int lv, int num)
{
    if (lv == n)
        return 1;

    if (dp[lv][num])
        return dp[lv][num];

    if (!num)
        dp[lv][num] += go(lv + 1, 1);
    dp[lv][num] += go(lv + 1, 0);

    return dp[lv][num];
}

int main()
{
    cin >> n;
    cout << go(1, 1) << "\n";
}