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

문제 링크: https://www.acmicpc.net/problem/20055

20055번: 컨베이어 벨트 위의 로봇

<문제 풀이> 시뮬레이션, deque

컨베이어의 회전은 deque를 이용하면 쉽고, 효율적으로 회전하는 걸 구현할 수 있습니다.

-> deque에 각 칸을 순서대로 넣고 회전시킬 때 맨 뒤에 있는 원소를 맨 앞으로 보내면 됩니다.

이제 문제에서 나온 조건을 그대로 구현하면 되는데

1. 로봇은 1 ~ N번 칸에만 있을 수 있고, N번 칸에 도착한 로봇은 없애버리면 됩니다.

2. 1번 칸에 로봇이 없고 내구도가 0이 아니면 매 단계마다 추가할 수 있습니다.

 

<C++ 소스 코드>

#include<iostream>
#include<deque>
#include<vector>
using namespace std;
 
class belt {
public:
    bool existRobot;
    int durability;
    belt(int existRobot, int durability) {
        this->existRobot = existRobot;
        this->durability = durability;
    }
};
 
deque<belt> dq;
int N, K;
int solve() {
    int ret = 0;
 
    int zeroCnt = 0;
    while (zeroCnt < K) { //4 내구도가 0인 칸의 개수가 k개 이상이라면 종료 
        //1
        ret++;
        dq.pop_front(); //buf 제거
        dq.push_front(dq.back()); //2N번을 1번으로
        dq.pop_back();
        dq.push_front({ false, 0 }); // buf 추가
        if (dq[N].existRobot) dq[N].existRobot = false; //로봇이 내리는 위치에 존재하면 로봇을 내린다
        //2
        for(int i = N - 1; i >= 1; i--) {//가장 먼저 올라간 로봇부터
            if (!dq[i].existRobot) continue; //로봇이 존재하면
            if (!dq[i + 1].existRobot && dq[i + 1].durability >= 1) {
                dq[i].existRobot = false;
                dq[i + 1].existRobot = true;
                dq[i + 1].durability--;
                if (dq[i + 1].durability == 0) zeroCnt++;
            }
        }
        if (dq[N].existRobot) dq[N].existRobot = false; //로봇이 내리는 위치에 존재하면 로봇을 내린다
        //3
        if (dq[1].durability != 0 && !dq[1].existRobot) {
            dq[1].existRobot = true; // 올리는 위치에 로봇을 올린다
            dq[1].durability--;
            if (dq[1].durability == 0) zeroCnt++;
        }
    }
 
    return ret;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> K;
    dq.push_front({false, 0});
    for (int i = 0; i < 2 * N; i++) {
        int d; cin >> d;
        dq.push_back({ false, d});
    }
    
    cout << solve();
    return 0;
}