릿코드 55. Jump Game

문제

https://leetcode.com/problems/jump-game/description/?source=submission-noac

LeetCode - The World's Leading Online Programming Learning Platform

접근

DP를 생각했다.

$ A_{n} $까지 점프할 수 있는 $ A_{n-1}, A_{n-4}, A_{n-7}  .... $ 이 있다면

$ A_{n-1} $까지 점프할 수 있는 $ A_{n-4}, A_{n-6}, A_{n-7} .... $ 이런 식으로 계속 찾아가서

$ A_{0} $에 도달할 수 있으면 dp를 True로 도달하지 못한다면 False로 업데이트했다.

그래서 $ A_{n} $까지 도달하는 모든 경우에 대해 로직을 실행하고, DP에 값이 있으면 다른 경우에서 실행했던 거니까 Short Cut으로 나오는 느낌으로 생각했다.

 

근데 DP가 필요 없었다.

$ A_{n-1} $ 까지 점프할 수 있는 원소는 $ A_{n} $ 까지 점프할 수 있는 원소를 포함한다. 예시로, $ A_{n} $까지 도달할 수 있는 $ A_{n-4} $가 $ A_{n-1} $을 도달하지 못할 수는 없다.

즉,  $ A_{n} $ 까지 도달하는 모든 경우에 대해 로직을 실행하지 않고, 그냥  $ A_{n} $부터 쭈욱 내려오면서 목표하는 원소만 바꾸면 된다.

 

처음 로직도 DP로 Short Cut이 있어서 막 늦는 건 아니지만 불필요한 부분들이 생겨서 DP없애는 것보단 느리다. 그리고 DP 없는 게 훨씬 간결하다.

일단 재귀를 짜게 되면 놓치는 경우를 잡아가면서 시간이 많이 걸린다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        target = len(nums) - 1
        for i in range(len(nums)-2, -1, -1):
            distance = target - i
            if nums[i] >= distance:
                target = i
        return True if target == 0 else False

 

# DP있는 로직

class Solution:
    dp = []
    def logic(self, nums, target):
        if target == 0:
            return True
        for i in range(target-1, -1, -1):
            distance = target - i
            if nums[i] >= distance:
                if self.dp[i] == True:
                    return True
                elif self.dp[i] == False:
                    continue

                if self.logic(nums, i):
                    self.dp[i] = True
                    return True
                else:
                    self.dp[i] = False
        return False

    def canJump(self, nums: List[int]) -> bool:
        leng = len(nums)
        self.dp = [ "x" for i in range(leng) ]
        return self.logic(nums, leng-1)