반응형

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

 

17071번: 숨바꼭질 5

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. pair<int,int> visited 배열을 만들어 각각 짝수번째 가장 일찍 도착하는 시간과 홀수번째 가장 일찍 도착하는 시간을 저장합니다.

 

2. K에 시간마다 i초씩 더해주면서 visited[ K + i ] % 2 == i % 2일 때 i의 최솟값을 Min에 저장합니다.

 

3. Min의 값이 987654321이 아니라면 Min을 출력하고, 그렇지 않다면 -1을 출력합니다.

 

[ 소스코드 ]

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, K;
pair<int,int> visited[500001];
 
int main()
{
    scanf("%d %d", &N, &K);
 
    if (N == K) {
        printf("0");
        return 0;
    }
 
    queue<pair<int, int>> q;
 
    q.push({ N,0 });
    for (int i = 0; i <= 500000; i++) {
        visited[i].first = 987654321;
        visited[i].second = 987654321;
    }
    visited[N].first = 0;
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        if (cnt % 2 == 0) {
            if (visited[cur].first < cnt) continue;
            visited[cur].first = cnt;
 
            if (cur > 0) {
                if (visited[cur - 1].second > cnt + 1) {
                    visited[cur - 1].second = cnt + 1;
                    q.push({ cur - 1,cnt + 1 });
                }
            }
            if (cur < 500000) {
                if (visited[cur + 1].second > cnt + 1) {
                    visited[cur + 1].second = cnt + 1;
                    q.push({ cur + 1,cnt + 1 });
                }
            }
            if (cur <= 250000) {
                if (visited[cur * 2].second > cnt + 1) {
                    visited[cur * 2].second = cnt + 1;
                    q.push({ cur * 2,cnt + 1 });
                }
            }
        }
        else {
            if (visited[cur].second < cnt) continue;
            visited[cur].second = cnt;
 
            if (cur > 0) {
                if (visited[cur - 1].first > cnt + 1) {
                    visited[cur - 1].first = cnt + 1;
                    q.push({ cur - 1,cnt + 1 });
                }
            }
            if (cur < 500000) {
                if (visited[cur + 1].first > cnt + 1) {
                    visited[cur + 1].first = cnt + 1;
                    q.push({ cur + 1,cnt + 1 });
                }
            }
            if (cur <= 250000) {
                if (visited[cur * 2].first > cnt + 1) {
                    visited[cur * 2].first = cnt + 1;
                    q.push({ cur * 2,cnt + 1 });
                }
            }
        }
 
        
    }
 
    int cnt = 1;
    int Min = 987654321;
    K++;
 
    while (K <= 500000) {
        if (visited[K].first != 987654321) {
            if (cnt % 2 == visited[K].first % 2 && cnt >= visited[K].first) {
                Min = min(Min, cnt);
            }
        }
        if (visited[K].second != 987654321) {
            if (cnt % 2 == visited[K].second % 2 && cnt >= visited[K].second) {
                Min = min(Min, cnt);
            }
        }
 
        cnt++;
        K += cnt;
    }
 
    if (Min != 987654321) {
        printf("%d", Min);
    }
    else {
        printf("-1");
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
[ 백준 ] 2830번 - 행성 X3 (C++)  (0) 2023.06.20
[ 백준 ] 5022번 - 연결 (C++)  (1) 2023.06.19
[ 백준 ] 2669번 - 직사각형 네개의 합집합의 면적 구하기 (C++)  (0) 2023.06.18

+ Recent posts

티스토리툴바