55. Jump Game

아놔.. 어제 ㅈㄴ길게 풀어놨느데 velog에 저장이 안되어있네요 진짜 눈물만 나네요..

처음에는 그냥 끝에 합만 보고 그 이후로 모든 index일 때 합이 더 큰걸로만 봤다가

class Solution {
    public boolean canJump(int[] nums) {
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
            
            if (total < i) {
                return false;
            }
        }
        
        return true; 
    }
}

submit한게 남아있네요...
틀렸읍니다

그렇게 뇌리에 스친 이름... backtrakcing...

class Solution {
    public boolean canJump(int[] nums) {
        return helper(nums, 0);
    }
    
    public boolean helper(int[] nums, int cur) {
        if (cur == nums.length - 1) {
            return true;
        }
        
        int next = Math.min(cur + nums[cur], nums.length - 1);
        
        for (int i = cur + 1; i <= next; i++) {
            if (helper(nums, i)) {
                return true;
            }
        }
        
        return false;
    }
}

Time limit이 걸려버렸네요...ㅎㅎ

코드가 엉망인줄 알아서 루션이 봤는데 걍 찐 타임리밋이었다는 점~

backtracking 저한테 어려운데 이거 ㅏ타임리밋걸릴 그런 친구 아닌거같은데...^^

런타임 O(2^n)이라네요

enum Index {
    GOOD, BAD, UNKNOWN
}

public class Solution {
    public boolean canJump(int[] nums) {
        Index[] memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;

        for (int i = nums.length - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], nums.length - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (memo[j] == Index.GOOD) {
                    memo[i] = Index.GOOD;
                    break;
                }
            }
        }

        return memo[0] == Index.GOOD;
    }
}

루션이 bottom-up

Runtime: 242 ms, faster than 30.61% of Java online submissions for Jump Game.
Memory Usage: 40.6 MB, less than 90.76% of Java online submissions for Jump Game.