# 백준 : 이친수(2193)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_2193_pinary%20number)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

#define MAX 90
long long int dp[MAX + 1] = {0,};

int main(void)
{
    int value;
    cin>>value;
    
    dp[0] = 0;
    dp[1] = 1;
    for(int i=2; i<=value; i++)
    {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    cout<<dp[value]<<endl;
    return 0;
}

풀이

잽싸게 풀어냈다. 사실 DP문제라고 하기보다는 '피보나치' 문제를 물어보는 것 같다.
규칙에 맞게 몇가지만 적어보면 이 문제가 피보나치를 규칙으로 하고 있다는 것을 쉽게 알 수 있다.
피보나치라는 것만 알고나면 문제를 푸는 것은 식은 죽 먹기.