[백준 20055번 컨베이어 벨트 위의 로봇 - 삼성 코테 기출 / C++]

www.acmicpc.net/problem/20055

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

오랜만에 풀어본 백준 문제..ㅎㅎ헤헤

 

처음 문제를 읽고.. 엥?! 뭐라는 거야~ 하고 몇 번 더 읽었던 것 같다.. ㅎㅎ (사실.. 항상 그런 것 같기도;)

어쨌든 문제를 읽었는데 아래와 같은 조건을 잘 만족해서 푼다면 될 것이라고 판단 하여... 코드를 작성하기 시작했다...💻

 

로봇 회전 과정

 

[STEP 0]

문제 조건 확인

문제 조건

 

위의 조건을 보았을 때 내려가는 위치에 로봇이 있는 경우에는 로봇이 반드시 땅으로 내려가야 한다. 로봇이 내려가는 위치에 가는 경우는 벨트가 움직이는 경우와 로봇이 스스로 움직이는 경우 두 가지가 있다. 그렇기 때문에 [STEP 1]과 [STEP 2]에 내려가는 위치의 로봇을 내려주는 작업을 수행할 것이다.

또한 어떠한 칸에 올라가거나 이동하면 내구도는 즉시 1만큼 감소한다. 이는 올라가는 위치에 로봇이 올라가거나, 혹은 로봇이 스스로 이동하는 경우를 들 수 있겠다. 그러므로 이 작업은 [STEP 2]와 [STEP 3]에서 진행할 것이다 후후. 

 

 

[STEP 1]

벨트가 한 칸 회전한다. 

void rotate()
{
    conveyer.push_front(conveyer.back());
    conveyer.pop_back();

    naegu.push_front(naegu.back());
    naegu.pop_back();
    conveyer[N - 1] = false;
}

이젠 문제를 풀다 보니..! 회전한다 하는 동사가 나오면 반사적으로 deque를 떠올리는 것 같다..ㅎㅅㅎ deque를 쓰지 않고 회전을 했다가 쉬운 문제를 돌아간 기억이 있기 때문ㅇ... 인가...?

 

deque를 사용해서 회전을 하면 회전 구현은 어 피스 오브 케잌이 되어버린다. 후후😏 구현이 더 쉽고 명확해진달까.. 진달래...(?)

그 이유는 회전이란 결국 첫 요소부터 끝 요소를 정하고 선형으로 나열 한경우 끝에 있는 요소는 맨 앞에 있던 요소의 앞으로 온다. 결국 맨 뒤 아이를 맨 앞으로 넣어주어 회전을 구혀한단 것이다. 킄

 

위의 코드는(rotate()) 로봇의 유무를 저장하는 컨베이어 벨트 deque와 내구성에 대한 값을 포함한 deque를 회전시키는 코드이다. 코드에서 보듯이 간단하게 맨 뒤에 있는 아이를 앞으로 넣어주고 맨 뒤에 있는 아이를 pop! 해주면 끝! 쏘 이 zi.

 

[STEP 2]

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

만약 이동할 수 없다면 가만히 있는다.

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

void move()
{
    for (int i = N - 2; i >= 0; i--) {
        if ((!conveyer[i + 1]) && (naegu[i + 1] > 0) && (conveyer[i])) {
            conveyer[i] = false;
            conveyer[i + 1] = true;
            naegu[i + 1]--;
        }
        conveyer[N - 1] = false;
    }
}

가장 먼저 벨트에 올라간 로봇부터라고 하니... 벨트의 N번째에 가까워지고 있다는 것일 거고! 난 N이 아니라 N-1이 벨트의 위에서 가장 끝에 있는 index이니 끝에서 두 번째인 N-1부터 0 번째까지 움직일 수 있는 로봇들을 움직여주었다.  움직일 수 있는 로봇들이란 i 번째 기준으로 i번째에 로봇이 있으며, i+1 번째에 로봇이 없고, 내구도 1 이상 남아있다는 것이다. 후후 로봇이 이동하는 경우에도 내구도를 빼주어야하니 1 감소 시켜준다. 

 

[STEP 3]

올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.

void put_robot()
{
    if (!conveyer[0] && naegu[0] > 0) {
        conveyer[0] = true;
        naegu[0]--;
    }
}

 

벨트의 시작점에(올라가는 위치) 로봇이 없으며 내구성이 1 이상이라면 로봇을 올려주고 내구성을 하나 뺀다. 로봇이 올라갈 때 내구도을 무조건 빼주어야 하니 ㅎㅅㅎ 내구도를 빼쥰다.‼️

 

[STEP 4]

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

int check()
{
    int count_ = 0;
    for (int i = 0; i < 2 * N; i++) {
        if (naegu[i] == 0)
            count_++;
    }
    return count_;
}

우선 벨트 전체를 체크해주어야 하니까 0부터 2*N-1까지의 칸의 내구도가 0인 곳을 카운트해준다. 카운트한 값이 K개 이상이라면 while을 종료하고 현재까지 진행한 단계를 출력해줄 것이다. ‼️

 

 

아래는 전체 코드이다..🌱

#include <deque>
#include <iostream>
#include <vector>

using namespace std;

deque<int> naegu;
deque<bool> conveyer;

int N, K, step;

void rotate()
{
    conveyer.push_front(conveyer.back());
    conveyer.pop_back();

    naegu.push_front(naegu.back());
    naegu.pop_back();
    conveyer[N - 1] = false;
}

void move()
{
    for (int i = N - 2; i >= 0; i--) {
        if ((!conveyer[i + 1]) && (naegu[i + 1] > 0) && (conveyer[i])) {
            conveyer[i] = false;
            conveyer[i + 1] = true;
            naegu[i + 1]--;
        }
    }
    conveyer[N - 1] = false;
}

void put_robot()
{
    if (!conveyer[0] && naegu[0] > 0) {
        conveyer[0] = true;
        naegu[0]--;
    }
}

int check()
{
    int count_ = 0;
    for (int i = 0; i < 2 * N; i++) {
        if (naegu[i] == 0)
            count_++;
    }
    return count_;
}

int main()
{
    step = 1;

    cin >> N >> K;
    for (int i = 0; i < 2 * N; i++) {
        int in;
        cin >> in;
        naegu.push_back(in);
        conveyer.push_back(false);
    }

    while (true) {
        rotate();
        move();
        put_robot();

        int c = check();
        if (c >= K) {
            cout << step << "\n";
            return 0;
        }
        step++;
    }

    return 0;
}