1871. Jump Game VII

문제: https://leetcode.com/problems/jump-game-vii/

Jump Game VII - LeetCode

 

 0번째 인덱스부터 시작해서 i + minJump <= j <= min(i + maxJump, s.length - 1)만큼 움직일 수 있을 때 맨 끝 인덱스에 도달 가능한지 구하는 문제다.  

 

 초기 상태에서 점프할 수 있는 구간은 minJump와 maxJump 사이 구간이다.  이때, minJump와 maxJump 구간에서 점프할 수 있는지 확인하는 방법은 구간의 카운트 값을 올려주는 것이다.  진입할 때 1을 증가시키고, 빠져나갈 때 1을 감소시키면 구간을 확인할 수 있다.  s[j]에서 값이 '0'인 경우에만 점프할 수 있으므로, cnt > 0이며 s[j]가 '0'인 경우에 점프가 가능하다.  맨 마지막 s.size() - 1 지점에서 s[j]가 '0'이고 cnt > 0이면 끝지점까지 도달할 수 있다는 뜻이다.

 

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        vector<bool> dp(s.size());
        dp[0] = true;
        int cnt = 0;
        for(int i = minJump; i < s.size(); i++){
            cnt += dp[i - minJump];
            if(i - maxJump > 0){
                cnt -= dp[i - maxJump - 1];
            }
            dp[i] = s[i] == '0' && cnt;
        }
        return dp.back();
    }
};