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

문제설명

N자리 이진수 중 0으로 시작하지 않고, 11을 포함하지 않는 이진수의 갯수를 구하는 문제

풀이방법

Top-down 풀이방식이다.
Cache array는 이중 배열로 구현하였다.
DP(a, b)의 정의 : 문제의 조건을 만족하고, a로 끝나는 b자리 이진수의 갯수
문제의 정답은 DP(0,N) + DP(1,N)이 된다.
기저조건은 a가 0, b가 1인 경우는 0, a가 1, b가 1인 경우는 1이다.
a가 1인 경우에는 DP(a, b) = DP(0, b-1)가 된다. 왜냐하면 1은 연속될 수 없기 때문이다.
a가 0인 경우에는 DP(a, b) = DP(0, b-1) + DP(1, b-1)가 된다.
한가지 유의할 점은 정답이 int의 범위를 넘어서기에, long long type으로 계산해야 한다.

점화식

\(DP(0, b) = DP(0, b-1) + DP(1, b-1)\)
\(DP(1, b) = DP(0, b-1)\)

위 점화식에 따라 코드를 작성하면 아래와 같다.

소스코드

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

long long cache[2][91];

long long DP(int a, int b){
    if(a == 0 && b == 1) return 0;
    if(b == 1) return 1;
    long long& ret = cache[a][b];
    if(ret != -1) return ret;
    if(a == 0) ret = DP(1, b-1) + DP(0, b-1);
    if(a == 1) ret = DP(0, b-1);
    return ret;
}

int main(){
    int N;
    cin >> N;
    memset(cache, -1, sizeof(cache));
    cout << DP(0, N) + DP(1, N);
}