Submission #3017214

---

Source Code Expand

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
//#include "../cxx-prettyprint/prettyprint.hpp"

std::unordered_map<int, int> memo;

int get_mininum_count(int N) {
    std::vector<int> withdrawals = {59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1};

    if (N == 0) {
        return 0;
    }
    if (memo.count(N) == 1) {
        return memo[N];
    }

    int min_count = N;
    for (int n : withdrawals) {
        if (n <= N) {
            min_count = std::min(min_count, get_mininum_count(N - n) + 1);
        }
    }
    memo[N] = min_count;
    return min_count;
}

int main() {
    int N;
    std::cin >> N;

    std::cout << get_mininum_count(N) << std::endl;
}

Submission Info

Judge Result