👀 문제
https://leetcode.com/problems/maximum-subarray/
👊 도전
1. 설계
- boolean DP를 이용한다.
- 방문한 곳(true)에서만 이동할 수 있는 범위를 체크한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
*
* @author HEESOO
*
*/
class Solution {
public boolean canJump(int[] nums) {
int n=nums.length;
boolean[] dp=new boolean[n];
dp[0]=true; // 시작점이니까 방문
for(int i=0;i<n-1;i++){
if(!dp[i]) continue; // 방문하지 않은 곳이면 패스
for(int j=1;j<=nums[i] && i+j<n;j++){ // i에서 뛸 수 있는 범위 체크
dp[i+j]=true; // 뛸 수 있는 곳은 true
}
}
return dp[n-1];
}
}
3. 결과
🤟 성공 🤟
BFS로 시도했으나 또 시간초과나서 DP로 수정해서 풀었다.
4. 설명
- DP를 이용한다
- boolean[] dp를 이용한다. dp[i]=true면 방문한 곳, false는 방문할 수 없는 곳이다.
- 0에서 시작하므로 dp[0]=true이다.
- dp[i]=false는 방문할 수 없는 곳이므로 뛸 수 없다. 따라서 continue로 패스한다.
- i에서 뛸 수 있는 곳을 j로 체크한다. dp[i+j]는 갈 수 있는 곳이므로 true로 바꾼다.
- 마지막 dp[n-1]이 true라면 도착할 수 있는 것이고, 아니면 없다는 뜻이다.