Problem link
https://leetcode.com/problems/frog-jump/
Problem Summary
처음엔 1칸을 뛸 수 있고 k칸 뛴 다음엔 k-1, k, k+1 칸을 뛸 수 있을 때 끝까지 점프할 수 있는지 확인하는 문제.
Solution
그냥 DP. N 크기도 작아서 대충 돌려주면 된다. 하드 중에서 아주 쉬운 문제.
DP[i, k]: i 인덱스에서 k칸 뛸 때의 가능 여부
위처럼 점화식 세우고 k-1,k,k+1 에 대해 돌려주면 된다. 위치가 아니라 인덱스로 저장했는데 map을 쓰면 위치로도 풀 수 있긴 하다.
Source Code
from functools import lru_cache
from typing import List
class Solution:
def canCross(self, stones: List[int]) -> bool:
@lru_cache(None)
def jump(idx, k):
if idx == len(stones) - 1:
return True
i = idx + 1
while i < len(stones) and stones[i] - stones[idx] < k - 1:
i += 1
while i < len(stones) and k + 1 >= stones[i] - stones[idx]:
if jump(i, stones[i] - stones[idx]):
return True
i += 1
return False
return jump(0, 0)