LeetCode Day 1
LeetCode Day 1 풀이
2026년 7월 22일 · 2 min read
LeetCode 문제 풀이
실버상위? 느낌의 인 듯
: 번까지 왔을 때 필요한 최소 횟수로 정의하고 1차원 를 짜면 된다
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 1, int(1e9));
dp[0] = 0;
for(int i = 0; i < n; i++){
int k = nums[i];
for(int j = 0; j <= i + k; j++){
if(j >= n) continue;
dp[j] = min(dp[j], dp[i] + 1);
}
}
return dp[n - 1];
}
};위와 거의 동일
: 번까지 올 수 있는가?로 놓고 를 돌리면 된다
다른 사람 솔루션을 보니 그리디로 에 풀 수 있는 듯
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 0; i < n; i++){
if(!dp[i]) continue;
int k = nums[i];
for(int j = 0; j <= i + k; j++){
if(j >= n) continue;
dp[j] = dp[i];
}
}
return dp[n - 1];
}
};bfs를 이용해서 구해주면 된다.
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int n = arr.size();
vector<int> dist(n + 1, -1);
queue<int> q;
dist[start] = 0; q.push(start);
while(q.size()){
auto cur = q.front(); q.pop();
if(!arr[cur]) return 1;
for(const auto& nxt : {cur - arr[cur], cur + arr[cur]}){
if(nxt < 0 or nxt >= n) continue;
if(dist[nxt] != -1) continue;
dist[nxt] = dist[cur] + 1; q.push(nxt);
}
}
return 0;
}
};