13. 유사 칸토어 비트열

https://school.programmers.co.kr/learn/courses/30/lessons/148652

단계마다 문자열이 확장되는 문제이므로 상위 단계에서 하위 단계로 내려가면서 현재 위치가 '0' 에서 만들어진 것인지 확인할 수 있다.
일단 첫번째 규칙성으로 (0-index) x % 5 == 2라면 무조건 '0' 이 위치하기 때문에 단계와 상관없이 0을 반환한다.
만약 x % 5 != 2라면 하위 단계에서 파생된 현재 단계의 x번째 원소가 '0' 인지 확인해봐야 하므로 x /= 5, n-- 을 처리한다.
단계가 모두 진행되었다면 1인 것이 확실하므로 1을 출력한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int solve(int n, ll x)
{
    if (x % 5 == 2) return 0;
    x /= 5, n--;
    if (n < 0) return 1;
    else return solve(n, x);
}

int solution(int n, ll l, ll r) 
{
    int ans = 0;
    for (ll x = l - 1; x <= r - 1; x++)
        ans += solve(n, x);
    
    return ans;
}