[LeetCode] 55. Jump Game c++

문제 설명

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

제한 사항

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

입출력 예

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

풀이

0번째 index가 시작점이고 nums배열 원소는 점프할 수 있는 최댓값이다.

num[0] : 2 → num[2] : 1→ num[3] :4 → num[4] 마지막 인덱스 도착!

마지막 인덱스까지 도착할 수 있다면 true,

원소 중간까지만 이동할 수 있다면 false를 반환한다.

 

여기서 중요한 식!

   i + nums[i]  를 도출할 수 있어야 한다. 

class Solution {
public:
    bool canJump(vector<int>& nums) {
        
        int mxcover = 0;
        
        for(int i=0 ; i<= mxcover ; i++)
        {
            if(mxcover >= nums.size()-1)
                return true;
            mxcover = max(mxcover , i + nums[i]);
        }
        return false;
    }
};