[Java] 동적계획법 - 점프 !

1. 문제

정수로 이루어진 배열 nums 가 주어지고, 0 번 인덱스에서 시작한다고 가정한다.

최대 현재 인덱스의 숫자 nums[i] 만큼 우측으로 이동이 가능하다고 할 때, 최종적으로 마지막 위치까지 도달할 수 있는지 여부를 논리형 값으로 출력하시오.

 

 

 

2. 입력 설명

• 0 < nums.length <= 1000
• 0 <= nums[i] <= 1000

 

 

3. 출력 설명

마지막 인덱스에 도착할 수 있는지 여부를 논리형 값으로 출력

 

 

 

4. 매개변수 형식

nums = {3, 4, 1, 1, 0, 3}

 

 

 

5. 반환값 형식

true

 

 

 

6. 입출력 예시 설명

아래와 같이 이동하면 마지막 위치인 5 인덱스까지 도달할 수 있다.

0 →  1 → 5

 

 

 

7. 힌트

DP 문제

 

 

 

 

8. 코드 구현

class Solution {
	public boolean solution(int[] nums) {
    	
        //최대 이동 가능한 위치를 매번 갱신
        // 최대 이동 가능한 위치를 기준으로 왼쪽은 자유롭게 모두 이동가능하기 때문
        
        int N = nums.length;
        int maxIndex = 0;
        
        for (int i = 0 ; i < N ; i++) {
        	
            // maxIndex가 현재위치에 도달한다면 최대 위치를 업데이트 시켜준다.
            if(maxIndex >= i) {
            	maxIndex = Math.max(maxIndex, i + nums[i]);
                
                // 끝에 도달한다면 true반환
                if(maxIndex >= N-1) {
                	return true;
                }
            } else {
            	return false;
            }
        }
        return false;
    }
}