2193번 이친수

문제 링크

이친수

문제 풀이

1부터 시작하고, 1이 연속으로 오지않는 N자리 이진수를 찾는 문제이다. 앞에 수가 1 이면 무조건 0 이 와야하고, 0 이오면 0, 1 모두 가능하다. 따라서 이전의 수와 자리수를 나타내는 값을 변수로 하여 재귀 호출한다.

구현

#include <iostream> 
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int N;
ll cache[101][2];

ll solve(int n, int num) {
    if (n == N - 1) return 1;

    ll& ret = cache[n][num];
    if (ret != -1) return ret;

    ret = solve(n + 1, 0);
    if (num == 0) ret += solve(n + 1, 1);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    memset(cache, -1, sizeof(cache));

    cout << solve(0, 1);
    return 0;
}