문제 푼 날짜 : 2021-11-04

문제

문제 링크 : https://www.acmicpc.net/problem/20055

접근 및 풀이

코드는 아래의 생각대로 구현하였다.

1. 컨베이어를 회전시킨다.
2. 컨베이어 위의 로봇들을 움직일 수 있다면, 한 칸씩 움직인다.
   2-1. 이 때, 로봇이 움직인 곳의 내구도가 떨어진다.
3. 컨베이어 제일 처음에 로봇을 놓을 수 있다면 놓는다.
   3-1. 이 때, 처음 위치의 내구도가 떨어진다.
4. 위 과정을 반복하다가 컨베이어 벨트의 내구도가 0인 것이 K개 이상이 되면 멈춘다.
   4-1. 위 과정을 반복한 횟수를 출력해준다.

적절한 자료구조를 떠올리는 것이 중요했다. 입력이 연속적으로 들어오는데 이 입력값을 이용하여 회전을 표현하기 위해서는 deque을 이용하는 것이 편하겠다는 생각을 했다.

코드

// 백준 20055번 : 컨베이어 벨트 위의 로봇
#include <bits/stdc++.h>

using namespace std;

int N, K, ans;
deque<int> durability;
deque<bool> onConveyor;

int check() {
    int ret = 0;
    for (int i = 0; i < durability.size(); i++) {
        if (durability[i] == 0) {
            ret++;
        }
    }
    return ret;
}

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

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

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

void putRobot() {
    if (durability[0] > 0) {
        onConveyor[0] = true;
        durability[0]--;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> K;

    for (int i = 0, num; i < 2*N; i++) {
        cin >> num;
        durability.push_back(num);
        onConveyor.push_back(false);
    }

    while (true) {
        if (check() >= K) {
            break;
        }
        ans++;
        rotate();
        move();
        putRobot();
    }
    cout << ans;
    return 0;
}

결과

피드백