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

문제

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

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

 

풀이 과정

1. 각 벨트의 칸의 상태를 저장하기 위한 방법 모색

2. 벨트를 회전하고, 로봇이 움직일 수 있다면 움직이며, 새로운 로봇을 추가하고, 벨트의 내구도가 0인 부분이 K이상 존재하면 종료

3. 종료 시 현재까지 반복된 횟수를 출력한다.

 

 

세부 풀이

(1)

구조체 cell을 만들어 현재 벨트 위치에 남은 내구도와 로봇이 위치하는지를 기록하는 인자를 만들어 이용했다.

 

(2)

우선 벨트를 순환시킨다. 이때 N위치에 로봇이 있다면 순환 후 N위치의 로봇은 사라진다. 이 부분이 중요했는데, 처음엔 1부터 2N 위치까지 계속 순환하는 형태의 구조라고 생각했다. 하지만 문제는 1의 위치에서 N위치로 로봇을 보내는 것이 목적인 기계 형태였다. 벨트는 가는 부분과 돌아오는 부분까지 2N만큼의 길이가 존재했던 것이다. 위 조건에 맞게 순환했을 때 N의 위치에 있는 로봇을 제거하고 다음 단계를 진행했다.

 

로봇은 1부터 N위치에 존재한다. 따라서 N위치부터 1의 위치까지 탐색을 진행하면 된다. 하지만 N위치의 로봇은 내려져서 비워져 있는 상태이며, N-1의 위치부터 탐색하여 1의 위치까지 탐색하도록 구현했다. (소스코드 상에서는 index가 0부터 시작하므로 N-2부터 0까지 탐색한다.)

로봇의 다음 칸에 로봇이 없고 해당 칸의 내구도가 1 이상(0보다 크다면)이라면 이동을 진행한다.

 

새롭게 놓는 위치의 벨트의 내구도가 0 이상이면 새로운 로봇을 배치하고 그렇지 않다면 그냥 다음 단계를 수행한다.

 

현재까지 벨트의 내구도를 조사하여 0이 된 내구도가 존재하는 칸의 수를 구하고 이 값이 K이상이면 종료한다.

 

(3)

종료하며 현재까지 반복된 횟수를 출력한다.

 

 

소스 코드

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

int N,K;

struct cell{
    int durability=0;
    bool is_full=false;
};

vector<cell> c_belt;

void Input(){
    cin >> N >> K;
    int temp;
    for(int i=0;i<2*N;i++){
        cin >> temp;
        cell one;
        one.durability=temp;
        c_belt.push_back(one);
    }
}

void solve(){
    int level=0;
    while(1){
        level++;
        //회전
        cell last_cell;
        c_belt[N-1].is_full = false;
        last_cell = c_belt[2*N-1];
        for(int i=2*N-2;i>=0;i--){
            c_belt[i+1]=c_belt[i];
        }
        c_belt[0]=last_cell;

        for(int i=N-2;i>=0;i--){
            if(c_belt[i].is_full){
                int nexti=i+1;
                c_belt[N-1].is_full = false;
                if(!c_belt[nexti].is_full && (c_belt[nexti].durability>=1)){
                    c_belt[i].is_full=false;
                    c_belt[nexti].is_full=true;
                    c_belt[nexti].durability--;
                    i++;
                }
            }
        }

        if(c_belt[0].durability>0){
            c_belt[0].durability--;
            c_belt[0].is_full=true;
        }

        int zero_cnt=0;
        for(int i=0;i<2*N;i++){
            if(c_belt[i].durability==0) zero_cnt++;
        }
        if(zero_cnt >= K){
            cout << level;
            break;
        }
    }
}



int main(){
    Input();
    solve();
    return 0;
}

 

 

결과 및 후기

그렇게 구현이 어렵지 않았으며 문제 이해가 조금 난해했던 문제이다. 컨베이어 벨트가 1부터 2N까지 로봇을 이동시키는 것이 아니라 1부터 N까지 로봇을 운반하고 벨트의 길이가 2N이라는 사실만 인지하면 간단히 구현할 수 있다.