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

문제

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

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

---

접근방법

1) 접근 사고

문제에서 주어진 그대로 구현하면 되는 문제엿다.

1.컨베이어벨트와 로봇들을 한 칸씩 회전시킨다

2.로봇들만 앞으로 한 칸 전진한다. 이때 내리는 위치에 가면 로봇이 사라진다.(내린다는 표현이 애매한거 같다. 컨베이어 벨트 밑으로 로봇을 내린다는 의미로 해석해서 푸는데 어려움이 있었다.)

3.첫 번째 위치에 가중치가 있고 로봇이 없다면 로봇을 둔다.

4. 1,2,3 작업을 가중치가 0개인 것들이 k개 이상일 때 까지 반복한다.

 

2) 시간 복잡도

O(n)

 

3) 배운 점

어려움 없이 구현했는데 내린다는 표현이 참... 애매하다. 컨베이어 벨트로 예시를 들어서 그런지 로봇이 그 안에서 반복되는걸로 잘못이해했다.

 

4) PS

---

정답 코드

/*
 * 1번 위치가 올리는 위치
 * n번 위치가 내리는 위치
*/
#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 100;
struct belt{
    int n , k;
    bool rboard[MAX * 2 + 1];
    int board[MAX * 2 + 1];
    belt(int n, int k) : n(n), k(k) {}
    
    void init(){
        memset(rboard, false, sizeof rboard);
        for(int i = 0; i < n * 2; i++){
            cin >> board[i];
        }
    }
 
    //보드와 로봇을 회전시키는 함수
    void rotateBoard(){
        int utmp = board[2 * n - 1];
        for(int i = (n * 2) - 1; i > 0 ; i--){
            board[i] = board[i - 1];
 
        }
        board[0] = utmp;
 
        bool tmp = rboard[2 * n - 1];
        for(int i = n * 2 -1; i > 0 ; i--){
            rboard[i] = rboard[i - 1];
        }
        rboard[0] = tmp;
 
        rboard[n - 1] = false;//이동한 뒤 내리는 위치는 로봇을 내려주어야 한다.
    }
 
    //컨베이어 벨트 위의 로봇들이 한칸 씩 앞으로 전진하는 함수
    void rotateRobot(){
        if(rboard[0] == false && board[0] > 0){
            if(rboard[2 * n - 1] == true){
                rboard[0] = true;
                board[0]--;
                rboard[2 * n - 1] = false;
            }
        }
        for(int i = n * 2 -1; i > 0; i--){
            if(rboard[i] == false && board[i] > 0){
                if(rboard[i - 1] == true){
                    rboard[i] = rboard[i - 1];
                    board[i]--;
                    rboard[i - 1] = false;
                }
            }
        }
        rboard[n - 1] = false; //이동한 뒤 내리는 위치는 로봇을 내려주어야 한다.
    }
 
    //컨베이어벨트위의 첫 번째 가중치가 존재하고 로봇이 없다면 로봇을 놔둔다.
    void putRobot(){
        if(board[0] > 0 && rboard[0] == false){
            rboard[0] = true;
            board[0]--;
        }
    }
 
    bool check(){
        int cnt = 0;
        for(int i = 0; i < 2 * n; i++){
            if(board[i] == 0)
                cnt++;
        }
        if(cnt >= k)
            return true;
        else
            return false;
    }
 
    void printBoard(){
        for(int i = 0; i < 2 * n; i++){
            cout << board[i] <<" ";
        }
        cout <<"\n";
 
        cout <<"=====board======="<<"\n";
    }
    void printrBoard(){
        for(int i = 0; i < 2 * n; i++){
            cout << rboard[i] <<" ";
        }
        cout <<"\n";
 
        cout <<"=====rboard======="<<"\n";
    }
};
 
int main(){
    int n, k;
    cin >> n >> k;
    belt op(n, k);
    op.init();
 
    int cnt = 1;
    while(1){
        op.rotateBoard();
        op.rotateRobot();
        op.putRobot();
        if(op.check()){
            cout << cnt <<"\n";
            return 0;
        }
        cnt++;
    }
    return 0;
}