반응형

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

 

5014번: 스타트링크

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. bfs를 이용하여 윗층과 아랫층으로 갔을 때의 층을 각각 queue에 push해 줍니다.

 

2. visited배열을 이용하여 이미 도착했던 층에 도착하면 무시해줍니다.

 

3. 원하는 층에 도착하면 버튼을 누른 횟수를 출력해줍니다.

 

4. 만약 queue가 빌 때까지 도착하지 못하면 use the stairs를 출력해줍니다.

 

[ 소스코드 ]

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
41
42
#include<iostream>
#include<queue>
 
using namespace std;
 
int F, S, G, U, D;
int visited[1000001];
 
int main()
{
    scanf("%d %d %d %d %d", &F, &S, &G, &U, &D);
 
    queue<pair<int,int>> q;
    q.push({ S,0 });
    visited[S] = 1;
 
    while (!q.empty()) {
        int cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        if (cur == G) {
            printf("%d", cnt);
            return 0;
        }
 
        if (cur+U <= F) {
            if (visited[cur + U] == 0) {
                visited[cur + U] = 1;
                q.push({ cur + U,cnt + 1 });
            }
        }
        if (cur-D > 0) {
            if (visited[cur - D] == 0) {
                visited[cur - D] = 1;
                q.push({ cur - D,cnt + 1 });
            }
        }
    }
 
    printf("use the stairs");
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1956번 - 운동 (C++)  (0) 2022.10.11
[ 백준 ] 23291번 - 어항 정리 (C++)  (0) 2022.10.10
[ 백준 ] 17406번 - 배열 돌리기 4 (C++)  (0) 2022.10.08
[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06

+ Recent posts

티스토리툴바