[코드업 3710] 369 게임 3 (Large Test Case)

굉장히 재미있는 문제였다. 로직 자체는 간단하다. 숫자에 369가 몇 개가 들어가 있는지 세기만 하면 된다. 그러나 이 문제에서는 1억개의 범위가 주어질 수 있고 제한시간은 2초 이내이다.

 

#include <iostream>

using namespace std;

int cache[100000003];

int getClab(const int& number) {
    if (cache[number]) {
        return cache[number];
    }
    else {
        int clab = 0;
        int target = number;

        while (target) {
            if (cache[target]) {
                clab += cache[target];
                break;
            }
            else {
                int tmp = target % 10;
                if (tmp != 0 && tmp % 3 == 0) clab++;
                target /= 10;
            }
        }
        return cache[number] = clab;
    }
}

int conquer(const int& a, const int& b) {
    if (a == b) {
        if (cache[a]) {
            return cache[a];
        }
        else {
            return cache[a] = getClab(a);
        }
    }
    else {
        int left = conquer(a, (a + b) / 2);
        int right = conquer(((a + b) / 2) + 1, b);
        return left + right;
    }
}

int main() {

    int a, b;
    cin >> a >> b;

    cout << conquer(a, b) << endl;
    return 0;
}

 

 

풀이법은 동적계획법과 분할과 정복을 동시에 사용하는 방법이다. 캐싱할 때 10으로 나누면서 캐싱이 되어있다면 가져다 쓰고, 없다면 계산하는 방식으로 로직을 구현했다.

또한 범위를 계속 절반으로 나누면서 수행하면 시간복잡도를 추가적으로 낮출 수 있다. 메모리는 100MB 정도 남았는데, 분할과 정복 부분에서 추가적으로 캐싱한다면 좀 더 빠른 속도로 수행할 수 있을 것이다.

 

독자 여러분들은 conquer 함수의 left, right도 캐싱해 보시라!