백준 알고리즘 11060번 : 점프 점프

링크

https://www.acmicpc.net/problem/11060

sol1) BFS

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main() {
  fastio;
  int n; cin >> n;
  vector<int> board(n + 1),dist(1001, -1);
  for(int i = 1; i <= n; i++) cin >> board[i];
  queue<int> Q;
  dist[1] = 0;
  Q.push(1);
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    if(cur == n) break;
    for(int i = 1; i <= board[cur]; i++){
      auto nx = cur + i;
      if(dist[nx] != -1) continue;
      if(nx < 1 || nx > n) continue;
      dist[nx] = dist[cur] + 1;
      Q.push(nx);
    }
  }
  cout << (dist[n] == -1 ? -1 : dist[n]) << "\n";
  return 0;
}

DP로도 되는 것 같긴한데 그냥 BFS로 풀었습니다.