[Array, Greedy] Jump Game II

 

점프게임 1과 조건은 같지만, last index까진 무조건 도착한다는 전제이다.

이때 0부터 시작해서 가장 적은 횟수로 last index까지 가려면 몇회가 소모되느냐이다

 

Greed를 쓸껀데 여기에서 착각하지 말아야 하는 점은 범위단위로 움직인다는 것이다.

count, now, max라는 세가지 변수를 두었다

순서대로 배열을 하나씩 돌면서 이를 업데이트 해줄 것이다.

max를 local마다 업데이트 할 것이고, 이는 각 지점에서 최대로 갈 수 있는 지점까지의 값이다

모든 배열에서 로직이 돌면 global max를 찾을 수 있다.

 

index=0에서 시작하니 count가 하나 올라가고 max가 변경된다.

이때 주의점은 범위단위라는 것인데, now와 실제 minmum이 별개로 움직인다는 뜻이다.

예컨데 문제에서 [ 2, 3, 1, 1, 4 ]는  index=0->1->4 순서로 last index에 도착할 수 있다.

그러나 now는 0->2->4 순서로 업데이트 된다.

now가 업데이트 된다는 뜻은 해당 범위까지의 체크는 끝났다는 뜻이기 때문이다

 

즉, now가 0에서 max가 2 이므로, index=1,2에 대해 검사를 진행한다 

이때 2에 도달하면 검사가 끝난셈이고, index=1,2중 더 max가 큰 값으로 알아서 설정되어있을테니 count를 하나 올려주는 것이다

그 다음엔 2부터 2의 max까지를 검사하면 된다.