백준 20055번: 컨베이어 벨트 위의 로봇 - 구현 C++

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

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

1. 문제설명

벨트가 회전함에 따라

각 벨트 번호의 내구도가 한칸씩 옮겨지고 로봇또한 한칸씩 옮겨지는 것을 구현하고,

벨트위에 있는 로봇을 옮길 수 있는지 확인한 후 한 칸씩 옮기는 것을 구현해야하는 문제이다.

 

이를 구현하기 위해

벨트의 번호에 따른 내구도를 나타내는 배열을 만들고

벨트의 번호에 따라 로봇이 있는지 여부를 나타내는 배열을 만들어서

회전시키는 것을 구현하면 된다.

 

단순 회전은 큐를 이용하면 쉽겠지만

이 문제에서는 각 로봇에 대해 접근을 해야하기 때문에

차라리 배열을 이용하는 것이 괜찮은 것 같다.

큐를 이용하면 회전을 빠르게 구현 할 수 있겠지만

결국 각 벨트 번호에 대한 로봇의 여부를 구하기 위해 인덱스접근하는데 O(n)이 필요하기 떄문이다.

 

 

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
int N, K;
void Input();

int durability[202];
bool robots[101];


void beltRotate(){
    int beltLast = durability[2*N];
    for(int i=2*N; i>1; i--){
        durability[i] = durability[i-1];
    }
    durability[1] = beltLast;

    for(int i=N; i>=1; i--){
        robots[i] = robots[i-1];
    }
    robots[N] = 0;


    for(int i=N-1; i>=1; i--){
        if(robots[i]){
            if(durability[i+1] > 0 && !robots[i+1]){
                durability[i+1]--;
                robots[i+1] = 1;
                robots[i] = 0;

                if(i+1 ==N) robots[i+1] =0;
            }
        }
    }

    if(durability[1] > 0){
        robots[1] = 1;
        durability[1]--;
    }
}

bool check(){
    int cnt = 0;
    for(int i=1; i<=2*N; i++){
        if(durability[i]==0){
            cnt++;
        }
    }

    return cnt >= K;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    Input();

    int turn = 1;
    while(1){
        beltRotate();
        if(check()){
            cout << turn << '\n';
            return 0;
        }
        turn++;
    }
}



void Input() {
    cin >> N >> K;
    for(int i=1; i<=2*N; i++){
        cin >> durability[i];
    }
}