LeetCode 45. Jump Game II

The link : leetcode.com/problems/jump-game-ii/

Jump Game II - LeetCode

문제 풀이는 다음과 같다.

 

1. 배열의 첫 번째 지점부터 시작된다. 이때 모든 배열의 점프 횟수는 0으로 초기화되어있다.

2 (now)	1	4	4	4
0	0	0	0	0

2. 첫 번째 지점에서 첫 번째 지점 + nums[0]이하까지 점프가 가능하다. 즉, 해당 이하의 점프 횟수는 +1이 된다.

2 (now)	3	1	1	4
0	1	1	0	0

3. 이제 다음 지점으로 가자. 두 번째 지점에서 두 번째 지점 + nums[1]까지 점프가 가능하다.

2	3 (now)	1	1	4
0	1	1	0 -> 2	0 -> 2

그런데 바로 다음칸인 세 번째 칸의 경우, 3을 거쳐서 점프를 하지 않아도 이미 한 번의 점프를 통해 도달할 수 있다.

때문에 점프횟수가 0이 아닌, 즉, 방문한 경험이 있는 지점은 그 횟수가 최소값이 보장되므로 내버려두면 된다.

하지만 점프횟수가 0인 경우, 즉, 방문한 적이 없는 경우는 무조건 현 위치를 거쳐야 최소 점프횟수로 방문이 가능하다는 의미이므로, 현재 점프 횟수 + 1을 저장해준다.

 

4. 만약 점프해서 도달할 수 있는 지역이 nums.size()-1이상인 경우 이미 답에 도달했다는 의미이므로, 종료하고 답을 출력해준다.

 

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<=1) return 0;
        int arr[1001] = {0,};
        for(int i=0; i<nums.size(); i++){
            for(int j=i+1; j<=i+nums[i]; j++){
                if(arr[j]!=0); // 가만 있어라
                else arr[j] = arr[i]+1;
                if(j==nums.size()-1) break;
            }
        }
        return arr[nums.size()-1];
    }
};