이번 문제는 BFS를 활용하여 해결할 수 있는 문제였다. 처음에 문제를 시도할 때에 큐를 사용하지 않아 시간 초과가 발생했다. BFS는 큐를 사용한다는 것을 기억하자.

• queue<pair<>>를 사용하여 큐에 현재 위치와 버튼 누른 수를 저장한다.
• BFS를 돌린다. 이 때 건물의 범위 내이고, 방문하지 않은 층수라면 큐에 push를 해주었다.

Code

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 1000001
using namespace std;

int f,s,g,u,d;
bool visited[MAX];
int cnt=0;

void Input(){
    cin>>f>>s>>g>>u>>d;
}

int BFS(int curr){
    memset(visited, false, sizeof(visited));
    queue<pair<int, int>> q;
    q.push(make_pair(curr, 0));
    visited[curr]=true;
    while(!q.empty()){
        int current=q.front().first;
        int count=q.front().second;
        q.pop();
        
        if(current==g)
            return count;
        if(current+u<=f&&!visited[current+u]){
            q.push(make_pair(current+u, count+1));
            visited[current+u]=true;
        }
        if(current-d>0&&!visited[current-d]){
            q.push(make_pair(current-d, count+1));
            visited[current-d]=true;
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    if(BFS(s)==-1)
        cout<<"use the stairs"<<endl;
    else
        cout<<BFS(s)<<endl;
    return 0;
}