BOJ 5014: 스타트링크

작성일

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

  • 3월동안 210문제 풀기 (14/210)
  • 수학으로 삽질하다가 결국은 BFS로 풀었음
  • 이런 류의 문제들은 대부분 Greedy로 간단히 풀리는듯함.
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
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;


typedef long long LL;
int main() {
  int F, S, G, U, D;
  cin >> F >> S >> G >> U >> D;
  vector<LL> visit(F+1);
  queue<int> q;
  q.push(S);
  visit[S] = 1;
  if(S == G) {
    cout << 0;
    return 0;
  }

  int move = 0;
  while(int curSize = q.size()) {
    move++;
    for(int sz = 0; sz < curSize; sz++) {
      int cur = q.front(); q.pop();
      int down = cur - D;
      int up = cur + U;
      if(down == G || up == G) {
        cout << move;
        return 0;
      }
      if(up <= F && !visit[up]) {
        visit[up] = 1;
        q.push(up);
      }
      if(down > 0 && !visit[down]) {
        visit[down] = 1;
        q.push(down);
      }
    }
  }
  cout << "use the stairs";
}