[LeetCode] 55. Jump Game

접근

• 처음에 백트래킹으로 풀었으나 TLE로 인해 승인되지 않았음
• 찾아본 결과 백트래킹+DP 로 풀거나 그리디 알고리즘을 사용하여 풀어야 함을 알게 되었음
• 그리디 알고리즘을 통해 문제를 해결
• https://www.youtube.com/watch?v=Yan0cv2cLy8 참고하였음

 

문제 링크

https://leetcode.com/problems/jump-game/

 

솔루션

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        nums_length = len(nums)
        point = nums_length-1

        for index in range(nums_length-1, -1, -1):
            # if available to move point from place of index
            if nums[index] + index >= point:
                point = index
        
        if point == 0:
            return True
        else:
            return False