45. Jump Game II

• Jump Game의 응용 문제.

• 처음에는 Jump Game에서 풀었던 방식을 이용하여 시도하였으나 실패했다.
• 최대로 점프 가능한 길이 maxJump 를 구하고
• 만약에 현재 점프 길이가 maxJump 보다 크면 값을 교체 + 점프한 횟수 jumpCount 를 증가시킨다.
• 이렇게 풀면 도달 가능한 경우의 수에 대한 jumpCount를 구할 순 있지만 최소 점프 횟수가 아닌 경우가 생길 수 있다.
• 예: [7,100,1] 의 경우 한 번에 점프 가능하지만 위의 로직에 의하면 점프한 횟수가 2회가 된다.

• 두번째 시도에서는 아래와 같은 방법을 사용했다.
• (1) 현재 위치 currPos를 마지막 위치 nums.size() - 1 로 지정한다.
• (2) currPos에 도달 가능한 가장 먼 위치 nextPos를 찾는다.
• currPos - 1 부터 역순으로 찾는다.
• 점프의 길이 nums[pos]가 현재 위치까지의 거리 currPos - pos 보다 커야 한다.
• (3) nextPos를 찾았다면 점프 횟수 jumpCount를 증가시키고 현재 위치를 다음 위치로 이동시킨다 currPos = nextPos.
• (4) 시작점 0에 도달할 때 까지 (2)~(3)을 반복한다.

• 만약에 array의 길이가 짧았다면 BFS + memoization을 사용해서 풀었을 것 같다.

class Solution {
public:
    int jump(vector<int>& nums) {
        int jumpCount = 0;
        int currPos = nums.size() - 1;
        while (currPos > 0) {
            int nextPos = -1;
            for (int pos = currPos - 1; pos >= 0; --pos) {
                if (nums[pos] >= currPos - pos) {
                    nextPos = pos;
                }
            }
            if (nextPos == -1) return -1;
            currPos = nextPos;
            ++jumpCount;
        }
        return jumpCount;
    }
};