백준 5014번: 스타트 링크

백준 5014번: 스타트 링크

 

DFS로 풀려하다가 DP도 사용해서 풀었다. 어렵게 풀지는 않았다.

현재 위치에서 스사트링크 위치까지 이동하는데 지정된 층수만큼 up하거나 down할 수 밖에 없다.

만약 엘레베이터로 갈 수 없다면 계단을 이용하라는 문구를 띄운다.

내가 생각한 조건은 다음과 같다.

 

1. up과 down을 했을 때 0층 초과 F층 이하 범위에서 엘레베이터가 움직이여야 한다.

2. up과 down으로 해당 층으로 이동가능 해야한다.

3. 이동하는 방법이 여러개 있을 때 먼저 도달하는 값이 최소값이다.

 

코드는 다음과 같이 작성했다.

 

이동했을 때 그 층이 이동 횟수의 최소값을 가지고 있어야하니까 dp는 모두 최고값인 1000001로 초기화를 했다.

시작층의 위치의 dp 값은 0으로 시작하여

up과 down 동시에 이동한다. 이동하는 부분은 dfs로 작성

up과 down으로 이동할 때 이전 층에서 이동값 +1씩 부여한다.

up과 down 도중에 스타트링크에 도달하면 해당 dp의 값이 최소값으로 바뀐다.

dfs가 끝나고나서 메인함수에서 출력을 할 것인데

스타트링크가 있는 dp값이 처음 설정했던 최대값이면 "use the stairs'

아니면 해당 dp값이 출력되게 만들었다.

 

// 5014 스타트링크
/*
    F : 건물 층 수
    G : 스타트링크 위치
    S : 현 위치
    U : 위층으로 움직임
    D : 아래층으로 움직임
 */
#include<iostream>
#include<cstring>
#define HIGH_FLOOR 1000001
using namespace std;

long long dp[HIGH_FLOOR];
long long F, S, G, U, D;
    

void DFS(long long dist, long long index){
    dp[index] = dist;
    if(index == G || index >= HIGH_FLOOR) return;
    if(index+U <= F && dp[index+U] > dist+1){
        DFS(dist+1, index+U);
    }
    if(index-D > 0 && dp[index-D] > dist+1){
        DFS(dist+1, index-D);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    // MAX FLOOR, CURRENT FLOOR, STARTLINK FLOOR, UP FLOOR, DOWN FLOOR
    cin >> F >> S >> G >> U >> D;

    //initialize
    memset(dp, HIGH_FLOOR, sizeof(dp));
    DFS(0, S);
    if(dp[G] >= HIGH_FLOOR){
        cout << "use the stairs\n";
    }
    else{
        cout << dp[G] << "\n";
    }

    return 0;
}