백준 20055 컨베이어 벨트 위의 로봇 C++

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

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

 

최종 코드

• GitHub https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ20055.cpp

hwayeon351/BEAKJOON-Algorithms

//
//  main.cpp
//  BJ20055_1
//
//  Created by Hwayeon on 2021/10/18.
//

#include <iostream>
#include <deque>
using namespace std;

int N, K;
struct Convey{
    int A;
    bool robot = false;
};
Convey cv;
deque<Convey> belts;
int cnt = 0;

void move_robots(){
    while(true){
        cnt++;
        
        //1. 벨트 한 칸 회전
        cv = belts.back();
        belts.pop_back();
        belts.push_front(cv);
        //내리는 곳에 로봇이 있는 경우, 로봇을 내린다
        if(belts[N-1].robot) belts[N-1].robot = false;
        
        //2. 가장 먼저 벨트에 올라간 로봇부터, 한 칸 이동
        for(int i=N-2; i>=0; i--){
            if(!belts[i].robot) continue;
            if(belts[i+1].robot) continue;
            if(belts[i+1].A > 0){
                belts[i+1].robot = true;
                belts[i+1].A--;
                belts[i].robot = false;
            }
        }
        //내리는 곳에 로봇이 있는 경우, 로봇을 내린다
        if(belts[N-1].robot) belts[N-1].robot = false;
        
        //3. 올리는 위치에 로봇을 올린다
        if(belts[0].A > 0){
            belts[0].robot = true;
            belts[0].A --;
        }
        
        //4. 내구도가 0인 칸의 개수 세기
        int gone = 0;
        for(int i=0; i<2*N; i++){
            if(belts[i].A == 0) gone++;
        }
        if(gone >= K) break;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> K;
    for(int i=0; i<2*N; i++){
        cin >> cv.A;
        belts.push_back(cv);
    }
    move_robots();
    cout << cnt << endl;
    
    return 0;
}

---

풀이 과정

풀이 시간 24분

 

#include <iostream>
#include <deque>
using namespace std;

int N, K;
struct Convey{
	//내구도
    int A;
    //올려진 로봇의 여부 체크
    bool robot = false;
};
Convey cv;

//컨베이어 벨트
deque<Convey> belts;

//단계
int cnt = 0;

void move_robots(){
    while(true){
    	//단계 카운팅
        cnt++;
        
        //1. 벨트 한 칸 회전
        //deque의 특성을 살려 가장 뒤에 있는 요소를 빼서 앞에 추가해주면 오른쪽으로 한 칸 회전을 구현할 수 있다
        cv = belts.back();
        belts.pop_back();
        belts.push_front(cv);
        
        //내리는 곳에 로봇이 있는 경우, 로봇을 내린다
        if(belts[N-1].robot) belts[N-1].robot = false;
        
        //2. 가장 먼저 벨트에 올라간 로봇부터, 한 칸 이동
        for(int i=N-2; i>=0; i--){
        	//해당 칸에 로봇이 없는 경우, 이동하지 않는다
            if(!belts[i].robot) continue;
            //이동할 위치에 이미 로봇이 있는 경우, 이동하지 않는다
            if(belts[i+1].robot) continue;
            
            //이동시킬 로봇이 있고 이동할 위치에 내구도가 0이상인 경우, 로봇을 이동시킨다
            if(belts[i+1].A > 0){
                belts[i+1].robot = true;
                //이동한 칸의 내구도가 감소한다
                belts[i+1].A--;
                belts[i].robot = false;
            }
        }
        
        //내리는 곳에 로봇이 있는 경우, 로봇을 내린다
        if(belts[N-1].robot) belts[N-1].robot = false;
        
        //3. 올리는 위치에 내구도가 0이상인 경우 로봇을 올린다
        if(belts[0].A > 0){
            belts[0].robot = true;
            //내구도가 1 감소한다
            belts[0].A --;
        }
        
        //4. 내구도가 0인 칸의 개수 세기
        int gone = 0;
        for(int i=0; i<2*N; i++){
            if(belts[i].A == 0) gone++;
        }
        
        //내구도가 0인 칸이 K개 이상인 경우, 과정을 종료한다
        if(gone >= K) break;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> K;
    for(int i=0; i<2*N; i++){
        cin >> cv.A;
        //컨베이어 벨트 칸 추가
        belts.push_back(cv);
    }
    //로봇 옮기기 시작
    move_robots();
    cout << cnt << endl;
    
    return 0;
}
//시간복잡도 = O(A*2*N*2*N) -> O(A*N^2), 공간복잡도 = O(N)

---

이전 풀이

풀이 시간 1시간 5분

 

//
//  main.cpp
//  BJ20055
//
//  Created by Hwayeon on 2021/07/12.
//

#include <iostream>
using namespace std;

int N, K;
int conv[200];
int robot[100];

void move_conv(){
    int temp = conv[2*N-1];
    for(int i=2*N-2; i>=0; i--){
        conv[i+1] = conv[i];
    }
    conv[0] = temp;

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

void move_robot(){
    if(robot[N-2] && conv[N-1] > 0){
        robot[N-2] = 0;
        conv[N-1]--;
    }
    for(int i=N-3; i>=1; i--){
        if(robot[i] && conv[i+1] > 0 && !robot[i+1]){
            robot[i] = 0;
            robot[i+1] = 1;
            conv[i+1]--;
        }
    }
}

void lift_robot(){
    if(conv[0] > 0){
        conv[0]--;
        robot[0] = 1;
    }
}

int check_conv(){
    int cnt = 0;
    for(int i=0; i<2*N; i++){
        if(conv[i]==0) cnt++;
    }
    return cnt;
}

int move(){
    int cnt = 0;
    while(true){
        //수행 단계 카운팅
        cnt ++;
        
        //1. 벨트와 로봇 한 칸 회전
        move_conv();

        //2. 로봇 이동
        move_robot();

        //3. 로봇 추가
        lift_robot();

        //4. 내구도 검사
        int k = check_conv();
        if(K <= k) break;
    }
    return cnt;
}

int main(int argc, const char * argv[]) {
    cin >> N >> K;
    for(int i=0; i<2*N; i++){
        cin >> conv[i];
    }
    cout << move() << endl;
    return 0;
}

문제에서 주어진 과정을 모듈로 나누어 차근차근 구현해 나가면 쉽게 풀 수 있다.

필자는 컨베이어 벨트의 내구도를 담은 2*N 크기의 배열 conv와 컨베이어 벨트 위에 있는 로봇의 위치를 담은 N 크기의 배열 robot을 만들어 주었다.

과정을 처리하는데 중요한 부분은 다음과 같다.

 

1. 컨베이어 벨트 이동 move_conv() -> O(n)

벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.

배열로 표현한 컨베이어 벨트인 conv의 값을 한 칸씩 이동시키기 위해 한 칸씩 값을 오른쪽으로 밀고, 마지막 요소 값을 첫 요소에 대입해준다.

conv의 이동처럼 배열로 표현한 로봇의 위치인 robot를 이동시킨다.

이때, 로봇이 내려가는 위치인 N-1로 이동되면 로봇은 바로 컨베이어 벨트에서 내려가므로 robot[N-1] = 0을 해준다.

또한, 좌측에서 우측으로 한 칸 회전시켰으므로 0번째 벨트에는 로봇이 존재하지 않기 때문에 robot[0] = 0을 해준다.

 

2. 로봇 이동 move_robot() -> O(n)

가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.

로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.

먼저, 내리는 위치 전에 로봇이 존재하고 robot[N-2] == 1, 내리는 위치의 벨트 내구도가 0보다 크다면, 로봇이 한 칸 이동하여 컨베이어 벨트에서 내리기 떄문에 robot[N-2] = 0과 conv[N-1]--를 해준다.

이후, 그 다음에 올라온 로봇들을 이동시킨다.

 

3. 로봇 올리기 lift_robot() -> O(1)

올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.

conv[0] > 0이면, conv[0]--와 robot[0] = 1을 해준다.

 

4. 내구도 체크 check_conv() - O(n)

conv를 탐색하여 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

 

시간복잡도는 K<=k가 될 때까지 while문이 반복되므로 O(n^2)이다.

공간복잡도는 robot과 conv 배열 사용으로 O(n)이다.