백준 20055 컨베이어 벨트 위의 로봇 c++ [컴공과고씨]

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

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

 

문제 정리

컨베이어 벨트가 있음

 

벨트 구성은 

이런식으로 벨트는 회전합니다.

올리는 위치에서 로봇을 올리고 내리는 위치에 로봇이 도착하면 로봇을 즉시 내립니다.

또한 벨트마다 내구도가 주어짐.

 

벨트 작동 순서

1. 벨트가 각 칸 위에 있는 로봇과 한 칸 움직임

2. 벨트에 먼저 올라간 로봇 부터 벨트가 움직이는 방향으로 로봇을 한 칸 움직임

   2-1) 움직이는 조건은 다음 칸의 내구도가 0보다 커야하고 로봇이 없어야 함.

3. 올리는 위치에 내구도가 0보다 크다면 로봇을 올림

4. 내구도가 0인 칸의 개수가 K개 이상이면 종료.

 

위 과정을 1 단계라고 하고 몇 번째의 단계 중에 종료가 되는지 구하는 문제.

 

 

문제 해결 방법

2N개의 배열을 선언을 하여 벨트를 만들어 주고 로봇이 있는지 여부도 배열로 선언해 줍니다.

 

1번째 단계 과정을 할 때 벨트를 직접 모두 한 칸 씩 옮기면 매 단계마다 엄청난 시간이 들게 됩니다.

그래서 저는 시작점과 끝나는 지점 즉, 올리는 위치와 내리는 위치 인덱스를 옮겨서 마치 벨트가 움직인 것처럼 만들어 주었습니다. 

그림으로 설명하면 

이런 식으로 시작 위치와 끝 위치 인덱스를 조작해서 문제를 해결 해 주었다.

1번째 작동은 start 위치와 end 위치를 -1씩 해주는데  (문제에서 인덱스 0부터 시작으로 해서 풀었음)

여기서 만약 인덱스가 0이라면 인덱스를 2N-1로 옮겨주는데 주의해야 한다. 

또한 문제에서 내리는 위치에 로봇이 있으면 바로 내리기 때문에 인덱스를 옮긴 후

end 위치에 로봇이 있으면 바로 내려주어야합니다.

 

2번째 작동은 로봇을 옮겨주는 과정이다.

여기도 마찬가지로 start 위치와 end위치를 잘 사용하면 해결 할 수 있다.

(첫 번째 단계에서는 올라간 로봇이 없기 때문에 수행하지 않는다.)

일단 맨 먼저 올라간 로봇이 당연히 end위치와 가깝기 때문에 end에서 부터 start까지 인덱스를 감소시키며 확인해줍니다.

1. 다음 위치에 로봇이 없는지

2. 현재 위치에 로봇이 존재하는지

3. 다음 위치의 내구도가 0보다 큰지

위의 3조건을 만족하면 로봇을 옮길 수 있으므로

다음 위치의 내구도를 감소시킨다.

내구도가 0이 되었다면 개수를 추가해주고 총 개수가 k개 이상이면 종료 flag에 표시를 해줍니다.

다음 좌표에 로봇을 추가하고 현재 좌표에 로봇은 없애줍니다.

 

3번째 작동은 로봇을 올리는 과정입니다.

올리는 위치 인덱스로 벨트 내구도 확인 후에 로봇을 올려주고 내구도 0의 개수가 k이상인지 확인해주면 됩니다.

 

위 전체 작동 과정이 단계이므로 위 3 작동이 다 완수 되면 result +1 을 해주면 됩니다.

 

전체코드

#include <iostream>
#include <vector>
using namespace std;
int n, k;
int belt[202];
bool robot[202] = {0};
int start_pos = 0;
int end_pos;
int inital_robot_pos = -1;
int result = 1;
int cnt = 0;
bool stop = false;
 
void rotation_belt(){
    if(start_pos == 0) // 0이면 맨 뒤의 인덱스로 옮김
        start_pos = 2 * n - 1;
    else
        start_pos--;
    
    if(end_pos == 0) // 0이면 맨 뒤의 인덱스로 옮김
        end_pos = 2 * n - 1;
    else
        end_pos--;
 
    if(robot[end_pos])
        robot[end_pos] = false;
}  
 
void move_robot(){
    if(inital_robot_pos != -1){ 
        // 첫번째 단계에서는 로봇이 없기 때문에 패스
        int idx = end_pos;
        for (int i = 0; i < n-1;i++){
            int next = idx; // 로봇이 갈 다음 위치
            if(idx == 0)
                idx = 2 * n - 1; // 현재 위치      
            else
                idx--; 
 
            if(!robot[next] && robot[idx] && belt[next] > 0){
                // 다음 위치에 로봇이 없는지
                // 현재 위치에 로봇 존재 하는지
                // 다음 위치의 내구도가 0보다 큰지
                belt[next] -= 1; // 내구도 감소
                if(belt[next] == 0){ // 내구도가 0이면
                    cnt++; // 내구도 0 개수 추가
                    if(cnt >= k){
                        stop = true; // 종료 flag
                        break;
                    }
                }
                robot[next] = true; // 다음 좌표 로봇 true
                robot[idx] = false; // 현재 좌표 로봇은 옮겼으니 false
            }
        }
        robot[end_pos] = false; // 내리는 위치 로봇 내려줌
 
    }
}
 
void put_robot(){
    if(belt[start_pos] > 0){ 
        belt[start_pos] -= 1; // 내구도 감소
        if(belt[start_pos] == 0){ // 종료 조건
            cnt++;
            if(cnt >= k){
                stop = true;
            }
        }
        robot[start_pos] = true; // 로봇 올림
        inital_robot_pos = 0; // 로봇 올리기 시작.
    }
}
 
int main(){
    cin >> n >> k;
    int temp;
    for (int i = 0; i < 2*n;i++){
        cin >> belt[i];   
    }
    end_pos = n - 1;
    while(!stop){
        rotation_belt();
        move_robot();
        put_robot();
        if(stop) // 종료
            break;
        result++; // 단계 완수
    }
    cout << result << endl;
    return 0;
}

체감 난이도	걸린시간
중	1h