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

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

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

이해를 포기할 수 밖에 없는 어려운 구현 문제이다.

크게 단계를 잘 쪼개야 한다.

 

1. 컨베이어 벨트를 돌린다(로봇과 별개)

2. 로봇을 한 칸씩 앞으로 이동 - 그 과정에서 내리는 칸에 있는 건 다 버리기

3. 로봇 추가

 

그리고 내구도는 로봇이 빠진다고 해서 다시 올라오지 않는다.

 

#include <iostream>
#include <queue>
#define MAX 220
using namespace std;
int n, k, s, e, cnt, answer;
// 내구성
int belt[MAX];
// 컨베이어벨트의 해당 칸에 로봇이 있음을 표시
bool visited[MAX];
// 로봇이 컨베이어 벨트에 올라간 순서 표시
queue<int> robot;
void move_belt() {
    s--;
    e--;
    if(s < 1) s = 2 * n;
    if(e < 1) e = 2 * n;
}

void move_robot() {
    int sz = robot.size();
    // queue.empty()로 탐색을 하면 안된다.
    for(int i = 0;i < sz;i++) {
        int cur = robot.front();
        visited[cur] = false;
        robot.pop();
        // 로봇 내리기
        if(cur == e) continue;
        
        int next = cur + 1;
        if(next > 2 * n) next = 1;
        // 로봇이 없으며 내구성이 1 이상 아니면 제자리
        if(belt[next] >= 1 && visited[next] == false) {
            belt[next]--;
            if(belt[next] == 0) cnt++;
            // 이동 후 로봇 내리기
            if(next == e) continue;
            visited[next] = true;
            robot.push(next);
        }
        else {
            visited[cur] = true;
            robot.push(cur);
        }
    }
}

void make_robot() {
    if(visited[s] == false && belt[s] >= 1) {
        visited[s] = true;
        belt[s]--;
        robot.push(s);
        
        if(belt[s] == 0) cnt++;
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> k;
    for(int i = 1;i <= 2 * n;i++) {
        cin >> belt[i];
    }
    
    s = 1;
    e = n;
    
    while(cnt < k) {
        answer++;
        move_belt();
        move_robot();
        make_robot();
    }
    
    cout << answer << '\n';
}