## 문제
[Jump Game - LeetCode](https://leetcode.com/problems/jump-game)
## 코드
### DP
문제를 보자마자 처음으로 떠올렸던 방법. 접근이 가능한 곳에서 그 다음으로 접근 가능한 곳들을 체크해나간다. 마지막 dp 배열의 마지막 원소가 true가 된다면 마지막 지점까지 도달 가능한 것.
직관적이긴 하지만 같은 원소에 반복적으로 접근하는 경우가 많아서 비효율적이다. (같은 지점에 도달할 수 있는 방법이 여러가지이므로...)
```typescript
function canJump(nums: number[]): boolean {
const canAccess = Array(nums.length).fill(false);
canAccess[0] = true; // 시작점은 접근 가능
for (let idx = 0; idx < nums.length; idx++) {
if (canAccess[idx]) {
// 현재 위치에서 다음에 도달 가능한 지점들 표시하기
for (let jump = 1; jump <= nums[idx]; jump++) {
const next = idx + jump;
if (next >= nums.length - 1) return true;
if (!canAccess[next]) canAccess[next] = true;
}
}
}
return canAccess[nums.length - 1];
}
```
### Greedy
우리가 구해야 하는 것은 경로가 아니라 "도달 가능한가?"이기 때문에 DP처럼 모든 과정을 기록할 필요는 없다. 따라서 현재 위치에서 도달 가능한 최대 지점을 계속 업데이트해나가는 Greedy 방식으로 풀면 시간복잡도 O(n) 으로 효율적으로 풀 수 있다.
```typescript
function canJump(nums: number[]): boolean {
let maximumPos = 0;
for (let curr = 0; curr <= maximumPos; curr++) {
const reachable = curr + nums[curr];
if (reachable >= nums.length - 1) return true;
maximumPos = Math.max(reachable, maximumPos);
}
return false;
}
```
## 참고
- [[Greedy]] (정리 예정)
- [[Dynamic Programming]] (정리 예정)