[리트코드]45. Jump Game II

class Solution:
    def jump(self, nums: List[int]) -> int:
        current_end = 0
        jump = 0
        far = 0
        
        for i in range(len(nums)-1):
            far = max(far, nums[i] + i)            
            
            if i == current_end:
                jump += 1
                current_end = far
                
                
        return jump

 

난이도 Medium

 

그리디나 dp문제 같다는 느낌을 받으며 풀이를 시작했다.

처음 있는 곳에서 다음 곳으로 가는 것을 고를때 다다음곳으로 갈수있는 범위가 가장 큰것을 고르려했다.

허나 생각처럼 구해지지 않고 예외 케이스에 계속 걸렸기에 답을 봤다.

 

위의 풀이는 문제 해설에 나온 풀이다. 그리디 알고리즘으로 풀었다고 하는데 솔직히 이해는 잘 안간다

내가 생각한 방식과 비슷하게 풀었을 것 같은데 조금 더 뒤에 다시 풀어봐야겠다..