leetcode(리트코드)55-Jump Game
leetcode(리트코드)55-Jump Game
leetcode 55 - Jump Game 문제입니다.
1. 문제
https://leetcode.com/problems/jump-game/
2. Input , Output
3. 분류 및 난이도
Medium 난이도 문제입니다.
leetcode Top 100 Liked 문제입니다.
4. 문제 해석
- 벡터로 주어진 요소만큼 점프할 수 있습니다. 점프를 해서 맨 끝요소로 도달할 수 있는지 여부를 리턴합니다.
5. code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
bool canJump(vector<int>& nums) {
bool* v = new bool[nums.size()];
memset(v,false,sizeof(bool) * nums.size());
v[0]=true;
for(size_t i =0;i<nums.size()-1;++i)
{
if(v[i]==true)
{
for(int j =0;j<=nums[i]; ++j)
{
if(i+j>nums.size()-1)
{
break;
}
if(v[i+j]==true)
continue;
else
v[i+j]=true;
}
}
}
return v[nums.size()-1];
}
};
6. 결과 및 후기, 개선점
0ms 100% 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
bool canJump(vector<int>& nums) {
int s=nums.size();
//벡터의 크기가 1개일 때
if(s==1){
return true;
}
int target=s-1;
for(int i=s-2; i>=0; i--){
if(i+nums[i]>=target){
target=i;
}
}
return target==0;
}
};
백트래킹 방법입니다. 만약 더 많이 점프할 수 있으면 해당 인덱스로 옮겨버립니다.
This post is licensed under CC BY 4.0 by the author.