[BOJ] 20055 : 컨베이어 벨트 위의 로봇

문제 링크

20055번: 컨베이어 벨트 위의 로봇 (acmicpc.net)

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

컨베이어의 회전을 구현해서 내구도가 0인 칸이 K개 이상 생겼을 때 수행중이던 단계가 몇 단계인지 출력하는 문제.

풀이

 컨베이어는 위의 그림처럼 1부터 2N번째까지 칸으로 이루어져있고, 1번 칸을 "올리는 위치" 즉, 새로운 로봇을 올리는 위치이고, N번 칸을 "내리는 위치" , 로봇이 내려오는 위치이다.

 컨베이어 벨트의 각 칸을 표현하는 방식은 여러가지가 될 것이다.

1. 2차원 배열을 이용해서 윗줄(1 ~ N), 아랫줄(N+1 ~ 2N)을 표현한다.

2. 1차원 배열을 이용해서 1 ~ 2N까지 표현한다.

3. 덱을 이용해서 1 ~ 2N까지 표현한다.

 셋 중에서 회전을 표현하기에 가장 적합한 방식은 3번 덱을 이용하는 방법이라고 나는 생각했다.

덱은 큐와 비슷한 자료구조이지만 앞 뒤 모두에서 값을 꺼낼 수 있기때문에 회전을 표현하기 쉽다.

덱의 맨 뒤에서 값을 꺼내서 덱의 맨 앞칸에 넣어주면 한 칸씩 회전한 후의 상태가 된다.

함수를 구현하기 전에 최소한으로 필요한 정보는 세가지 정도가 되겠다.

• 해당 칸에 로봇이 이미 있는지에 대한 정보(①)
• 해당 칸의 내구도가 얼마인지에 대한 정보(②)
• 현재 로봇들의 위치에 대한 정보(③)

로봇이 이동하려면 이동하려는 칸에 로봇이 있으면 안되고 내구도가 1이상이어야 이동할 수 있다.

그리고 로봇을 순차적으로 이동시켜야하기 때문에 로봇의 위치를 올려진 순서대로 저장해 두어야한다.

컨베이어 각 칸마다 로봇의 유무와 내구도는 컨베이어가 회전함에 따라 같이 회전해야하므로 앞에서 말한대로 덱으로 만들어서 정보를 저장했다.

 1. 컨베이어의 회전

컨베이어의 회전은 앞서 말했듯이 덱의 특성을 이용해서 쉽게 표현할 수 있다.

위의 ①, ② ,③ 번 정보를 모두 바꿔주어야한다. ①, ②번은 단순히 그냥 한 칸씩 회전 시켜주면 된다.

③번은 모든 로봇의 위치를 +1 시켜주고 만약 2N번째 로봇은 2N+1로 이동하는게 아니라 1번으로 이동한다.

그런데 나는 배열이 아닌 덱으로 표현했기 때문에 0번 인덱스부터 정보가 들어있다. 따라서 문제에 있는 사진에서 인덱스를 하나씩 작게 생각해야한다. 0번이 시작 인덱스이고 2N-1이 마지막 인덱스이다.

로봇이 2N번째 칸으로 이동하게 되면 0번 칸으로 이동시켜준다.

그리고 로봇이 이동했을 때 N-1 번째 칸. 즉 "내리는 위치"라면 로봇을 내려준다. 이때 N-1번째 칸의 로봇의 유무는 '무'로 바꿔준다.

2. 로봇의 이동

③번에 로봇들에 대한 정보가 저장되어있다. 이때 올려진 순서대로 로봇들에 대한 정보를 저장해두어야 문제 조건대로 로봇들을 이동시킬 수 있다. 0번 인덱스에 제일 먼저 올려진 로봇의 위치를 저장했다.

0번 인덱스부터 현재 올려져있는 로봇의 개수만큼 인덱스를 돌면서 만약 다음칸에 로봇이 없고, 내구도가 1이상이라면 로봇의 위치를 +1 해주고 다음칸의 내구도를 -1 해주었다.

만약 이동한 칸이 N-1번째 칸 "내리는 위치"라면 로봇을 내려야한다.

3. 로봇 올리기

로봇은 무조건 "올리는 위치"에만 올라가므로 컨베이어 0번 칸에 로봇을 올려준다.

이때 0번칸의 로봇 유무를 '유'로 바꿔주고, 0번칸의 내구도를 1 깎는다.

새로 들어온 로봇은 ③번 로봇 정보들 맨 뒤칸에 새로운 로봇에 대한 정보를 추가한다.

4. 내구도가 0인 칸 >= K 라면 종료

내구도의 변화가 생기는 과정은 2. 로봇의 이동, 3. 로봇 올리기 이다.

로봇을 이동시킬 때와 로봇을 올릴 때 해당 칸의 내구도를 깎았을 때 내구도가 0이면 내구도가 0인 칸의 개수를 +1 시켜준다.

내구도가 0인 칸의 개수가 K이상이면 종료하고 그때의 단계를 출력한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100 + 5;
deque<int> A;
int N, K;
deque<bool> deq;
deque<int> Robot;
int Zero = 0;
 
void rotation();
void moving();
void Add_robot();
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
    for (int i = 0; i < 2 * N; i++) {
        int a;
        cin >> a;
        A.push_back(a);
    }
 
    for (int i = 0; i < 2 * N; i++)
        deq.push_back(false);
    int turn = 0;
 
    while (true) {
        turn++;
        rotation();
        moving();
        Add_robot();
        if (Zero >= K)
            break;
    }
    cout << turn << "\n";
    return 0;
}
void rotation() {
    deq.push_front(deq.back());
    deq.pop_back();
    A.push_front(A.back());
    A.pop_back();
 
    deque<int> Remain;
    int idx = -1;
    for (int i = 0; i < Robot.size(); i++) {
        Robot[i]++;
        if (Robot[i] >= 2 * N)
            Robot[i] = 0;
        if (Robot[i] == N - 1)
            idx = i;
    }
    if (idx != -1) {
        Robot.erase(Robot.begin() + idx);
        deq[N-1] = false;
    }
}
 
void moving() {
    vector<int> idx;
    for (int i = 0; i < Robot.size(); i++) {
        int next = Robot[i] + 1;
        if (next >= 2 * N)
            next = 0;
        if (A[next] > 0 && !deq[next]) { //다음칸으로 이동 가능하면
            deq[Robot[i]] = false;
            deq[next] = true;
            Robot[i] = next;
            A[next]--;
            if (!A[next])
                Zero++;
            if (next == N - 1) {
                deq[next] = false;
                idx.push_back(i);
            }
        }
    }
    for (int i = 0; i < idx.size(); i++)
        Robot.erase(Robot.begin() + idx[i]);
}
 
void Add_robot() {
    if (A[0] <= 0)
        return;
    Robot.push_back(0);
    A[0]--;
    if (A[0] == 0)
        Zero++;
    deq[0] = true;
}