Yep, you are right. There is simple O(n) algorithm:

    intt n; cin >> n; n++;
    intt pw2 = 0, pw3 = 0, pw5 = 0, next2 = 2, next3 = 3, next5 = 5, res = 1;
    dp[0] = 1;
    for (intt i = 1; i < n; i++) {
        dp[i] = res = min (next2, min (next3, next5));
        if (next2 == res) {
            next2 = 2 * dp[pw2 + 1];
            pw2++;
        }
        if (next3 == res) {
            next3 = 3 * dp[pw3 + 1];
            pw3++;
        }
        if (next5 == res) {
            next5 = 5 * dp[pw5 + 1];
            pw5++;
        }
    }
    cout << res << endl;

Idea is same with fofao_funk's.

You should use O(N) memory, since for each popped element (at most N) you put 3 other in the set.