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

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

3 6

10 10 10 10 10 10

　 

 Output 

31

▶ 시뮬레이션 문제로, 예외처리만 주의하면 어렵지 않게 풀 수 있는 문제였습니다.

  "로봇은 올라가는 위치(up)에만 땅에서 올라가고, 내려가는 위치(down)에서만 땅으로 내려갈 수 있다."

- 컨베이어 벨트 후 첫번째 위치에서 로봇을 올리는 시도를 할 수 있습니다.

  N번째 위치에서 로봇이 내려가서 없어지기에, N+1 ~ 2N까지에는 로봇이 없는 것입니다.

  즉, 첫번재에 로봇이 올려지고 N번째 위치에 도달하면 로봇이 없어지기에

  컨베이어 벨트에는 한 단계가 끝났을 때에는 최대 N - 1개의 로봇이 존재할 수 있습니다.

  (N + 1번째부터 로봇이 삭제되는 것이 아닙니다.)

- 로봇은 N번째에서 없어지는 각 단계에서 로봇이 없어지는 경우

    ① 컨베이어 벨트가 회전해서 N-1번째에 놓여있던 로봇이 N번째가 되는 경우

    ② N-1번째의 로봇이 이동해서 N번째에 도달하는 경우

    ex) 단계 시작 전 N-2번째에 로봇이 있는 경우, 

          컨베이어 벨트 회전 + 로봇 이동으로 N번째에 도달하여 삭제될 수 있습니다.

 

시뮬레이션

① belt = [1 2 1 2 1 2] 

    - 벨트가 회전하면서 올라가는 위치와 내려가는 위치 변경

      → belt = [1 2 1 2 1 2] ▶ UP(1), DOWN(3) → UP(6), DOWN(2)

    - 올라간 로봇이 없으므로 로봇 이동 X

    - 첫번째 위치 UP(6)에 로봇을 올립니다. (내구성 감소)

      → belt = [1 2 1 2 1 1] ▶ 로봇 위치 robot[] = {6}

 

② belt = [1 2 1 2 1 1]

    - 벨트가 회전하면서 올라가는 위치와 내려가는 위치 변경

      → belt = [1 2 1 2 1 1] ▶ UP(6), DOWN(2) → UP(5), DOWN(1)

    - 올라간 로봇이 먼저 올라간 순서대로 이동 시도

      → 로봇 위치 robot[] = {1} (내구성 감소) → belt = [0 2 1 2 1 1]

          내려가는 위치 DOWN(1)이므로 해당 로봇은 없어집니다. → robot[] = { }

    - 첫번째 위치 UP(5)에 로봇을 올립니다. (내구성 감소)

       → belt = [0 2 1 2 0 1] ▶ 로봇 위치 robot[] = {5}

        ▶ 내구성 "0" belt 개수 = 2 (종료)

 

코드 분석

- 올라가는 위치 up, 내려가는 위치 down

    - 컨베이어 벨트 belt[]의 순서를 바꾸지 않고, up/down 변수로 회전 구현

- 컨베이어 벨트 내구도(hp), 로봇 존재 여부

- 로봇의 위치를 담기 위한 Queue

    - 먼저 올라간 순서대로 처리하기 위해서 FIFO 구조 사용

      (문제 내용상, 먼저 올라간 로봇이 제일 먼저 사라질 수 밖에 없습니다.)

 

- 각 단계 종료 후, 내구도 "0"의 컨베이어 벨트 개수를 확인합니다.

 

① 컨베이어 벨트 회전

- 실제 belt[]의 순서를 바꾸지 않고, 올라가는 위치(up) / 내려가는 위치(down)를 바꿉니다.

  (올라가는 위치와 내려가는 위치만 알면 되기 때문)

  * up/down 모두 한칸씩 감소하며, 원형으로 회전되는 것에 주의합니다.

- 컨베이어 벨트 회전이 끝나고, 내려가는 위치(down)에 로봇이 존재 여부 확인

  (현재 올려져 있는 로봇 중에서는 가장 먼저 올려진 로봇에 해당됩니다.)

② 로봇(들)을 이동시킵니다.

- 먼저 올라간 로봇부터 이동시키기 위해, Queue에 가장 먼저 push된 로봇부터 확인합니다.

   * 이동 결과에 따라 Queue에 다시 들어가기 때문에 초기 Queue 크기만큼만 이동 시도 합니다.

- 다음 위치로 이동하지 못하는 경우, 현재 위치 그대로 존재합니다.

- 이동 가능한 경우, 로봇의 위치가 변하며, 내구성도 변하기에 확인합니다.

   이동된 경우에는 "내려가는 위치"인지 확인합니다.  

③ 로봇을 첫번째 위치에 올리기 시도합니다.

- 첫번째 위치에 로봇이 존재하거나, 내구도가 안되는 경우는 올릴 수 없습니다.

- 올리기 성공한 경우에 내구성 확인하는 것에 주의

---

#include <stdio.h>
#include <queue>
using namespace std;
 
const int MAX_N = 100 + 5;
const int MAX_K = 2 * MAX_N;
int N, K, up, down, cnt, ans;
struct Belt {
    int hp;
    bool isRobot;
}belt[MAX_K];
queue<int> robot;
 
void rotateBelt() {
    up = up - 1;
    if (up == 0) up = 2 * N;
 
    down = down - 1;
    if (down == 0) down = 2 * N;
 
    // 새로운 내려가는 위치에 로봇이 존재하는 경우
    if (belt[down].isRobot) {
        belt[down].isRobot = false;
        robot.pop();
    }
}
 
void moveRobot() {
    int size = robot.size();
    for (int i = 0; i < size; ++i) {
        int cur = robot.front(); robot.pop();
        int next = cur + 1;
        if (next > 2 * N) next = 1;
 
        // 다음 위치의 내구성과 로봇 존재 여부 확인
        if (belt[next].hp <= 0 || belt[next].isRobot) {
            // 로봇의 위치 변화 없이 Queue에 다시 push
            robot.push(cur);
            continue;
        }
 
        // 이동가능한 경우
        belt[next].hp--;
        if (belt[next].hp == 0) cnt++;
 
        belt[cur].isRobot = false;
 
        // 내려가는 위치인 경우
        if (next == down) continue;
        belt[next].isRobot = true;
        robot.push(next);
    }
}
 
void placeRobot() {
    // 로봇이 존재하거나 내구성 안되는 경우
    if (belt[up].isRobot || belt[up].hp <= 0)
        return;
 
    // 로봇 올리기
    belt[up].isRobot = true;
    robot.push(up);
    // 내구도 감소
    belt[up].hp--;
    if (belt[up].hp == 0) cnt++;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= 2 * N; ++i) {
        scanf("%d", &belt[i].hp);
    }
    up = 1, down = N;
    while (cnt < K) {
        ans++;
        rotateBelt(); // 1. 컨베이어 벨트 회전
        moveRobot(); // 2. 로봇 이동
        placeRobot(); // 3. 로봇 올리기
    }
    printf("%d\n", ans);
}