Project Euler #14 : 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

VI dp(1000001, -1);
int ubak(llong num) {
    if (num <= 1000000 && dp[num] != -1) return dp[num];
    int ret = 0;
    if (num == 1) return ret;
    if (num % 2) ret = 1 + ubak(3 * num + 1);
    else ret = 1 + ubak(num / 2);
    return ret;
}
 
int main() {
    int mmax = -1;
    int maxIndex;
    rep(i, 1, 1000001) {
        dp[i] = ubak(i);
        if (mmax < dp[i]) {
            mmax = dp[i];
            maxIndex = i;
        }
    }
    cout << maxIndex;
}

메모이제이션 없이 하니 10초쯤 걸렸다.

하니깐 0.5초

map으로 하면 좀 더 빨라질듯?