[BOJ] 2193

이친수

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

분류

• Silver 3

• 다이나믹 프로그래밍

해법

DFS를 이용하여 점화식을 찾아 보면
N번째 이친수의 개수는 N - 1번째 이친수의 수와 N - 2번째 이친수의 수를 합한 것과 같음을 알 수 있습니다.
어디선가 본 적이 있는 성질일 것입니다. 풀어보시고 확인하세요.

정답 코드

#include <iostream>
using namespace std;

// same with N+1-th fibo
long long pinary(int N)
{
    long long pin[2] = {0, 1}; // fibo 1 and fibo 2
    
    for (int i = 3; i <= N + 1; i++)
    {
        long long next = pin[0] + pin[1];
        pin[0] = pin[1];
        pin[1] = next;
    }
    return pin[1];
}

int main(void)
{
    int N;
    cin >> N;
    cout << pinary(N);
    return 0;
}