BAEKJOON 2193 - 이친수

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

dynamic programming 방법 중 하나인 memoization 으로 쉽게 풀 수 있는 문제입니다. 

우선 이친수를 구할 수 있는 재귀함수를 만들고 memoization 을 사용하는 방법으로 풀었습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
ll cache[91][2];
ll getPinaryNumber(int digit, int num)
{
    if (digit == 1)
        return 1;
 
    ll& ret = cache[digit][num];
    if (ret != 0)
        return ret;
 
    if (num == 1)
        ret += getPinaryNumber(digit - 1, 0);
    else
        ret += getPinaryNumber(digit - 1, 1) + getPinaryNumber(digit - 1, 0);
 
    return ret;
}
 
int main()
{        
    int digit;
    cin >> digit;
    memset(cache, 0, sizeof(cache));
    cout << getPinaryNumber(digit, 1) << endl;
 
    return 0;
}