[LeetCode] 45. Jump Game II

class Solution {
public:
    int jump(vector<int>& nums) {
        
        int start = 0;
        int answer = 0;
        while(start<nums.size()-1){

            int tmp = 0;
            int best = nums[start+1];
            int nextIdx = 0;

            if(start+nums[start]>=nums.size()-1) {
                answer++;
                break;
            }
            for(int j=start+1; j<=start+nums[start]; j++){
                if(nums[j]+tmp >= best){
                    best = nums[j]+tmp;
                    nextIdx = j;
                }
                tmp++;
            }
            start = nextIdx;
            cout<<"next : " << nextIdx<<endl;
            answer++;
        }
        return answer;
    }
};

오랜만에 알고리즘 문제를 풀었다.
최근에 학교 알고리즘 수업에서 greedy 와 탐색에 대해서 배우고 있는데, 관련된 문제를 한 번 풀어보고 싶어서 leetcode 에서 greedy 태그를 검색해서 문제를 풀어봤다.

greedy는 위치한 상황에서 최선의 선택을 하고, 그 선택을 번복하지 않는 방법이다.
이 문제에서는 최소한의 점프횟수로 목표지점에 도달하는 것이 관건인데,
해당 상황에서 사용할 수 있는 점프횟수를 얼마나 사용했는지 + 도착지점에서 점프할 수 있는 최대 거리가 얼마인지를 기준으로 최선의 선택지를 골랐다.
탐색 과정에서 마지막에 인덱스 범위를 넘어가는 것을 고려하지 못해서 문제를 겪었다.