← 24주차 · 최종 모의고사와 실전 전략
보통그리디DP

DP 또는 그리디 판단

정수 배열 nums가 주어져요. nums[i]는 인덱스 i에서 앞으로 최대 몇 칸 뛸 수 있는지를 뜻해요. 인덱스 0에서 시작해 마지막 인덱스까지 가는 데 필요한 최소 점프 수를 반환해요. 끝까지 갈 수 없으면 -1을 반환해요.

매 칸에서 '지금 점프로 닿을 수 있는 범위' 안에서 다음 점프로 가장 멀리 갈 수 있는 곳을 기준으로 삼으면, 각 구간을 한 번의 점프로 처리하는 그리디가 성립해요. O(n)이에요.

DP로도 풀 수 있지만(dp[i] = i까지 최소 점프), 그리디가 더 빠르고 짧아요. 어느 쪽을 고를지 스스로 판단해 봐요.

예시

예시 1
입력
nums = [2, 3, 1, 1, 4]
출력
2
설명
0에서 1로(1칸) 뛰고, 1에서 마지막으로(3칸) 뛰면 두 번이에요.
예시 2
입력
nums = [0, 2]
출력
-1
설명
첫 칸에서 한 칸도 못 뛰어 끝까지 갈 수 없어요.
예시 3
입력
nums = [1]
출력
0
설명
이미 마지막 칸에 있어요.

제한 사항

  • 1 ≤ nums.length ≤ 100,000
  • 0 ≤ nums[i] ≤ 10,000
curEnd(지금 점프로 닿는 끝)와 farthest(다음에 닿을 수 있는 가장 먼 곳)를 둬요. 각 칸에서 farthest를 갱신하고, i가 curEnd에 닿으면 점프 수를 늘리고 curEnd를 farthest로 옮겨요. 이때 farthest가 제자리면 더 못 가니 -1이에요.
javascript
function minJumps(nums) {
  const n = nums.length;
  let jumps = 0;
  let curEnd = 0;
  let farthest = 0;
  for (let i = 0; i < n - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === curEnd) {
      if (farthest <= i) return -1;
      jumps++;
      curEnd = farthest;
    }
  }
  return jumps;
}
이전 문제격자 탐색 + 상태 관리
다음 문제그래프 + 최적화
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.