[Leetcode] 1387. Sort Integers by The Power Value (C++)

https://leetcode.com/problems/sort-integers-by-the-power-value/

Sort Integers by The Power Value - LeetCode

[풀이] DP

홀수인경우 kx3 + 1 , 짝수인경우 k/2를 해서 1이 될때까지 만드는 문제

최대 1000개의 값들을 계산해야 하기 때문에 시간복잡도 예상이 안되서 

DP로 풀었는데 완전탐색 해도 풀린다고 한다.

dp 배열을 처음에 4000 크기정도만 해줘도 될거라고 생각했는데 계속 런타임 에러가 나서

500000까지 바꿔주었다. 1000 이하의 k 값을 1로 만드는 과정에서 k가 상당히 커질수도 있는 것 같다.

 

  
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
 
    int dp[500000];
 
    int sol(int k) {
 
        if (k == 1) return 0;
 
        int& ret = dp[k];
        if (ret != 0) return ret;
 
        if (k % 2) ret = 1 + sol(3 * k + 1);
        else ret = 1 + sol(k/2);
        
        return ret;
    }
 
    int getKth(int lo, int hi, int k) {
        vector<pair<int,int>> a;
        for (int i = lo; i <= hi; i++) a.push_back(make_pair(sol(i),i));
        
        sort(a.begin(), a.end());
    
        return a[k-1].second;
    }
};

 

https://github.com/has2/Algorithm/blob/master/leetcode/1387.cpp