[Array, Greed] Jump Game

각 element의 값은 해당 index로부터 element의 값만큼 떨어진 index로 점프할 수 있음을 나타낸다

이때 마지막 index로 갈 수 있는지의 여부를 묻는 문제이다.

 

이렇게 단순히 배열을 순회하는 케이스에서는 greedy로 풀어내면 수월하다.

target을 배열의 마지막 index로 설정한다.

 

target을 배열의 맨뒤부터 설정하고, 각 원소로부터 target까지 갈 수 있는지 여부를 판단한다

한곳에서라도 방법이 있다면 해당 위치로 타겟을 바꾸어 검사한다

 

예컨데 [3,2,1,0,4] 은 false인데, 0,1,2,3 위치에서 어떻게 하더라도 index=4로 갈 수 없기 때문이다.

만약 [3,3,1,0,4] 라면 true일 것이다. index=1의 위치에서 index=4로 갈 수 있기 때문이다.

그 다음엔 index=1이 타겟이 되고, index=1보다 작은 위치에서 index=1로 갈 수 있는 방법이 있는지 봐야한다

index=0이 3이므로 갈 수 있어서 true가 되는 것이다.