Leet Code - 45. Jump Game II

leetcode.com/problems/jump-game-ii/

 

Answer

 

그리디 방식으로 문제를 풀어야 한다고 한다.

 

맨처음에 풀어야한다고 할 때 

1) nums[i]만큼 탐색

2) nums[i]만큼 이동한거보다 더 큰 값으로 이동하는 값이 있으면 그 값으로 이동 

이라는 생각을 했었는데

 

방향성은 어느정도 맞았지만 구현해내는 방법이 틀려 풀어내지 못했었다.

 

farthest라는 값을 통해 가장 멀리 간 값을 구해내고

curr_end에 i가 도달하면 curr_end를 farthest로 변경해주는 방식이다.

 

www.youtube.com/watch?v=cfdwhSmLt3w&t=443s