백준 20055번: 컨베이어 벨트 위의 로봇 [C++]

작성일 | In
골드 V 골드 V

문제

컨베이어 벨트 위의 로봇

풀이

로봇은 $N + 1$번째 칸 부터 $2N$번째 칸에는 올라가지 않습니다.

벨트를 $1$부터 $2N$까지 일자로 둡시다. 회전하는 것은 $2N$을 맨 앞으로 보내는 것으로 생각하면 됩니다.

로봇은 가장 오른쪽에 있는 것이 가장 먼저 올라간 것이므로 로봇의 위치를 연결 리스트로 관리해주면 됩니다.

코드

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
#include <bits/stdc++.h>
using namespace std;

struct ConveyorBelt {
    int n;
    list<int> robots;
    deque<int> durability;

    ConveyorBelt(int n) : n(n), durability(2*n) {}

    int broken = 0;

    void rotate() {
        durability.push_front(durability.back());
        durability.pop_back();

        for (auto it = robots.rbegin(); it != robots.rend(); it++)
            (*it)++;
        if (not robots.empty() and robots.back() == n - 1)
            robots.pop_back();
    }

    void move() {
        for (auto it = robots.rbegin(); it != robots.rend(); it++) {
            if (it != robots.rbegin() and *prev(it) == *it + 1)
                continue;
            if (durability[*it + 1] == 0)
                continue;

            (*it)++;
            if (--durability[*it] == 0)
                broken++;
        }
        if (not robots.empty() and robots.back() == n - 1)
            robots.pop_back();
    }

    void putRobot() {
        if (durability[0] == 0)
            return;

        robots.push_front(0);
        if (--durability[0] == 0)
            broken++;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    ConveyorBelt belt(N);
    for (int i = 0; i < 2*N; i++)
        cin >> belt.durability[i];

    int answer = 0;
    while (belt.broken < K) {
        answer++;
        belt.rotate();
        belt.move();
        belt.putRobot();
    }

    cout << answer;

    return 0;
}

C++ deque는 연결 리스트가 아니므로 임의 원소 접근이 $O(1)$에 가능합니다.

그러나 vector와 rotate를 써서 회전을 구현한 것 보다 유의미하게 빠르지 않았습니다.

편한 대로 구현하면 될 듯합니다.

백준 20055번: 컨베이어 벨트 위의 로봇 [C++]