[백준 2193번 이친수/ C++]

 

www.acmicpc.net/problem/2193

2193번: 이친수

 

문제 조건

 

 

0	1	2	3	4	5	6	7	8	9
0	1	1	2	3	5	8	13	21	34

 

각 자리수 마다 만들어지는 이진수의 개수는 위의 표와 같다! 명확히 식이 들어나는 문제이다...ㅎㅅㅎ!!!👍🏻

 

dp[i] = dp[i-1] + dp[i-2]인 것을 확인할 수 있다. 

 

#include <iostream>

using namespace std;

long long dp[91];
int main()
{

    dp[1] = 1;
    dp[2] = 1;
    int N;

    cin >> N;

    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];

    cout << dp[N];

    return 0;
}