컨베이어 벨트 위의 로봇

작성일 | In

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

문제 링크

삼성 코딩테스트 기출 문제이다. 문제의 조건에 맞춰 정확히 구현해야하는 시뮬레이션 문제이다.
문제에서 주어진 4가지 과정을 해석해보면 아래와 같다.

  • 로봇은 컨베이어 벨트가 움직일 때 함께 움직이고, 이후 조건을 만족할 시 한 번 더 움직일 수 있다.
  • 로봇이 컨베이어 벨트에 올라갈 수 있는 칸과 내려갈 수 있는 칸은 각각 하나씩이다.
  • 올라가는 칸이 비어있고 내구도가 1이상이라면 반드시 로봇이 올라가야하고, 내려가는 칸에 로봇이 있는 상태에서 컨베이어 벨트가 움직이거나, 로봇이 움직인다면 반드시 내려가야 한다.

만약 컨베이어 벨트 앞,뒤면 상태를 나타내는 conveyor 배열을 만들고, 이를 매 단계마다 직접 한 칸씩 전부 옮겨가는 방식으로 구현한다면 시간초과가 발생할 것이라 생각했다. 따라서 배열의 각 요소를 전부 옮기지 않고, 내려가는 칸과 올라가는 칸을 기억하는 변수를 만들어 이 변수의 값을 조절하는 방식을 택했다. 아울러 로봇의 위치를 기억하는 visited 배열을 따로 만들어서 로봇의 움직임을 제어했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

vector<int> conveyor;
vector<bool> visited;
int s,e;
int broken, step;
int n, k;

int main(void) {
    scanf("%d %d", &n, &k);

    conveyor.resize(2*n);
    for(int i=0; i<2*n; ++i)
        scanf("%d", &conveyor[i]);

    visited.resize(2*n);
    s = 0; e = n-1;
    while(broken < k) {
        ++step;
        
        // 컨베이어 움직이기 전 내릴 위치에 로봇 있으면 내리기
        if(visited[e])
            visited[e] = false;

        // 컨베이어 움직임
        s = (s + 2*n - 1) % (2*n);
        e = (e + 2*n - 1) % (2*n);

        int te = e, ts = s;
        while(te != ts) {
            if(visited[te]) {
                if(te == e)
                    visited[te] = false;
                else {
                    int ne = (te + 1) % (2*n);
                    if(!visited[ne] && conveyor[ne] > 0) {
                        visited[te] = false;
                        visited[ne] = true;
                        conveyor[ne] -= 1;
                        if(conveyor[ne] == 0)
                            ++broken;
                    }
                }
            }
            te = (te + 2*n - 1) % (2*n);
        }

        // 올라가는 위치에 로봇 놓기
        if(!visited[s] && conveyor[s] > 0) {
            visited[s] = true;
            conveyor[s] -= 1;
            if(conveyor[s] == 0)
                ++broken;
        }
    }
    printf("%d", step);
}
0%