Leet Code - 45. Jump Game II

알고리즘/알고리즘 문제 복기

내일도무사히 2021. 3. 26. 07:25

Answer

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

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

1) nums[i]만큼 탐색

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

이라는 생각을 했었는데

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

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

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