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

- 문제 ( 20055번 ) : 컨베이어 벨트 위의 로봇

• 링크 : https://www.acmicpc.net/problem/20055

• 컨베이어벨트 위에 로봇을 올리는 위치와 로봇을 내리는 위치가 정해져있다. 또한 컨베이어벨트의 내구도도 설정이 되어있어 내구도가 있는 컨베이어벨트의 위치만 사용할 수 있다.

  이 때 컨베이어벨트를 작동시켜 일을 하다가 종료되었을 때 몇 단계가 진행중이었는지 출력하는 프로그램 작성.

  • 종료조건 : 컨베이어벨트의 내구도가 0인 칸의 개수가 K 개 이상인 경우

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄에 컨베이어벨트의 길이 ( N ), 종료개수 K 입력
• 둘째 줄에 공백을 사이에 두고 각 컨베이어벨트의 내구도를 입력받음.

[ 출력 ]

• 컨베이어벨트의 K개의 위치에서 내구도가 0이 되어 작동을 멈췄을 때 진행중이던 단계 출력.

---

- 문제 풀이

• 이번 문제는 알고리즘 분류에서도 보다시피 "simulation" 문제이다.

  simulation 문제는 해결해야하는 문제에서 주어진 과정들을 따라 수행한 후 나오는 결과를 구하면 되는 유형의 문제이다.

  이번 문제에서 주어진 과정은 아래와 같다.
  

  즉, 위에 보이는 과정들을 종료조건을 만날때까지 수행하면서 결과를 도출하면 되는 문제이다.

• 나는 이 문제를 풀면서 총 4 가지의 step 을 각각 함수로 구현해주었다.
  그리고 함수 구현 이전에 컨베이어벨트의 내구도가 저장되어있는 deque 하나, 컨베이어벨트 위에 로봇이 있는지 확인하는 bool deque 하나를 선언해 준 후 함수를 구현해주었다.

  step1. 컨베이어벨트 회전 ( void rotate() )

  • 회전하면 변경되는 정보는 다음과 같다.

    1. 내구도 : 0 -> 1 -> . . . -> 2N-1 -> 2N 으로 내구도 회전
    2. 로봇 존재 여부 : 0 -> 1 -> . . . -> 2N-1 -> 2N 으로 회전

  • 이렇게 컨베이어벨트를 회전시키기 위해 앞뒤로 원소를 삽입할 수 있는 deque 자료구조를 사용했다.

    deque 를 사용하면 가장 뒤에 있는 원소를 앞에 삽입하면 회전되는 효과를 얻을 수 있다.

  • 그리고 이때 로봇이 무조건 내리는 위치인 N번째 (index로 하면 N-1번째) 위치는 언제나 로봇이 내려질테니 false 로 설정.

  step2. 벨트가 움직이는 방향으로 로봇 이동

  • N번째 위치에서는 무조건 로봇이 내려질테니 이동을 고려할 로봇이 없음.
    => 즉, 1번째 ~ N-1번째 위치에 대해서만 고려해주면 됨.
  • 이동조건은 다음과 같다.

    1. 이동하려는 칸에 로봇 존재 X
    2. 이동하려는 칸에 내구도 1 이상 남아있어야 함.
    3. 내가 현재 관심있는 위치에 로봇이 있어야 함.

  • 이 때도 step1 과 같이 N번째는 언제나 로봇이 내려오기 때문에 false 로 설정

  step3. 벨트 위에 로봇 올리기

  • 로봇을 올릴 수 있는 조건

    1. 올리는 위치의 칸의 내구도가 0 이상
    2. 올리는 위치에 로봇이 없어야 함.

  step4. 내구도가 0인 칸의 개수 확인 ( 종료조건 확인하기 위함. )

  • 컨베이어벨트의 내구도를 확인하면서 0이면 count 증가시킨 후 최종 count 를 return

• 이렇게 문제에서 주어진 각각의 과정들을 함수로 구현한 후, main 문에서 종료조건을 만날때까지 step1 ~ step4 까지 반복해준 횟수를 출력해주면 문제 해결!

---

- 최종 코드

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

// 전역변수 설정 (N : 컨베이어벨트 길이, K : 내구도가 0인 칸의 최대 개수)
int N = 0, K = 0;

// 컨베이어벨트 내구도 관리 공간
deque<int> hp;

// 컨베이어벨트위에 물건 존재여부 관리
deque<bool> conv;

// step1. 벨트 회전 (로봇과 함께)
// deque 를 사용하다 보니 deque 의 가장 마지막 원소를 가장 앞에 push 하면 회전이 됨.
void rotate() {
    // 내구도를 회전
    hp.push_front(hp.back());
    hp.pop_back();

    // 물건 존재여부역시 함께 회전
    conv.push_front(conv.back());
    conv.pop_back();

    // 내리는 위치인 N-1 위치는 언제나 로봇이 도착하면 바로 내리니 false 설정
    conv[N-1] = false;
}

// step2. 로봇 이동 (벨트가 움직이는 방향으로)
// N번째 위치에서는 무조건 로봇이 내려질테니 1번째 ~ N-1번째에 대해서만 로봇을 움직여주면 됨.
void move_robot() {
    for(int i = N-2; i >= 0; i--) {

        // 이동 조건 : 이동하려는 칸에 로봇 존재 x && 이동하려는 칸의 내구도 1 이상 && 현재 i 위치에 로봇이 있으면
        if((conv[i+1] == false) && (hp[i+1] > 0) && (conv[i] == true)) {
            conv[i+1] = true;
            conv[i] = false;
            hp[i+1] --;
        }

        // 이동할 수 없다면 현재 위치의 가만히 있으므로 변화 X
        // N번째 위치에 로봇이 도달했다면 바로 내려줘야하므로 N번째 위치의 conv 는 언제나 false
        conv[N-1] = false;

    }
}

// step3. 벨트 위에 로봇 올리기 (올리는 위치의 칸이 내구도가 0이 아니면)
void put_robot() {
    // 올리는 위치의 칸의 내구도가 0이 아니고 && 로봇이 없다면 로봇 올림 (내구도 1 감소)
    if((conv[0] == false) && (hp[0] > 0)) {
        conv[0] = true;
        hp[0] --;
    }

}

// step4. 내구도가 0인 칸의 개수 확인 (return : 내구도가 0인 칸의 개수)
int check() {
    int count = 0;
    for(int i = 0; i < 2*N; i++) {
        if(hp[i] == 0) {
            count ++;
        }
    }

    return count;
}

int main() {
    // 컨베이어벨트 길이 N 과 종료조건 K 입력
    cin >> N >> K;

    // A1 ~ A2n 까지 입력
    for(int i = 0; i < 2*N; i++) {
        int input = 0;
        cin >> input;

        // 컨베이어벨트 내구도 관리 queue 에 저장
        hp.push_back(input);

        // 아직 로봇이 없으니 컨베이어벨트 위치에 false 로 저장
        conv.push_back(false);
    }

    // 현재 몇단계 수행중인지 저장하는 변수 선언
    int step = 1;

    // 종료조건과 일치하기 전까지 step1 ~ 4 까지 반복수행한다.
    while(true) {
        // step 1 ~ 4 수행
        rotate();
        move_robot();
        put_robot();

        // 종료조건 : 내구도가 0인 칸의 개수가 K 개 이상
        int count = check();
        if(count >= K) {
            cout << step << endl;
            return 0;
        }

        // 종료조건에 걸리지 않으면 단계를 올리고 step 1 다시 진행
        step++;
    }

    return 0;
}