[알고리즘] 리트코드 1696. 점프 게임 VI c++ // set, deque dp

https://leetcode.com/problems/jump-game-vi/

 

* 그냥 dp

pos N에대해 k번반복문 == O(N * K) -> 100억 -> 터진다.

 

 

 

vector<int> nums; 
int k;
int dp[100000+4];

class Solution {
public:
    int dfs(int pos){ //pos에서 그때의 최대점수
        if(pos==nums.size()-1){
            return nums[pos];
        }
        if(pos>=nums.size()){ //배제
            return -987654321;
        }
        if(dp[pos]!=-1){
            return dp[pos];
        }

        dp[pos]=-987654321; //최대값구하기에서 dp 초기값 == INT_MIN, 0으로하면 안됨(0보다 작은값가능)
        for(int i=1;i<=k;++i){
            dp[pos]=max(dp[pos],dfs(pos+i)+nums[pos]);
        }
        return dp[pos];
    }
    int maxResult(vector<int>& _nums, int _k) {
        nums=_nums;
        k=_k;
        memset(dp,-1,sizeof(dp));
        return dfs(0);
    }
};

 

* 최적화 dp

- dp[pos] : pos도달시, 점수의 최대값

- set : pos에 도달시, 가능한경우(k칸 이하) 중 이전 점수중 최대값을 저장할거임

num을 순회하면서 , 점프불가능한 경우를 지우고, 이전값중 최대값 + 현재점수를 dp에 저장한다.

시간복잡도 : O(N) * O(log k ) // set 에서 k번 삽입,삭제

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        vector<int> dp(size(nums), INT_MIN);           // set기본정렬 == 오름차순임!
        multiset<int> s ({ dp[0] = nums[0] });         // set dp[0] = nums[0] and insert it into set
        for(int i = 1; i < size(nums); i++) {
            if(i > k) s.erase(s.find(dp[i - k - 1]));  // k칸초과로 점프 불가능!
            //cout<<*rbegin(s)<<" ";
            s.insert(dp[i] = *rbegin(s) + nums[i]);    // choose element with max score and jump from that to the current index
        }
        return dp.back();
    }
};

 

* 덱 dp : O(N)

set에서는 최대값만 조회하면 되는데, 최소값을 쓸데없이 저장하고 있어서 logN의 시간이 걸리는것임.

-> 덱을이용해서 최대값만 남기고 최소값을 제거해버리면 O(1)에 조회가 가능함! // 

dp[i] : i 위치에 도달하는데 최대점수 // 이거보다 작은값들은 필요없으므로 팝함

덱에는 idx를 저장함.