20055 - 컨베이어 벨트 위의 로봇

이 문제는 제시한 과정을 코드로 구현해 작동 과정을 시뮬레이션하여 답을 구해야 하는 시뮬레이션 문제이다.

작동 과정을 정리해 보면, 길이가 N인 컨베이어에 길이 2N짜리 벨트가 돌아가고 있고 벨트의 각 칸에는 내구도가 정해져 있다. 내구도가 0이면 로봇을 올리거나 로봇이 앞으로 움직일 수 없다.

항상 컨베이어의 시작 지점에 로봇을 놓고(내구도가 남아있는 경우), 끝 지점에 로봇을 내려놓는다. 로봇을 놓으면 내구도가 1 감소한다.

제일 처음에 컨베이어에 들어온 로봇부터, 자신의 앞 칸에 로봇이 없고 내구도가 1 이상이면 앞으로 움직인다. 로봇이 움직이면 옮긴 칸의 내구도는 1 닳는다.

컨베이어는 단계별로 1칸씩 항상 움직인다. 내구도가 0인 벨트 칸의 개수가 K개 이상이면 작동을 멈춘다.

🔗 문제 링크

코드

먼저 필요한 전역변수들을 선언하자. N, K값과 내구도 및 로봇 위치를 저장할 int wear[205], bool belt[205]를 선언한다. IDX(x)는 현재 컨베이어 기준으로 x번째 위치가 벨트의 몇 번째 칸에 대응되는지 구하는 매크로 함수이다.

#include <iostream>
using namespace std;

#define IDX(x) ((2*N - offset + x) % (2*N))

int N, K;
int wear[205];
bool belt[205];

다음으로 필요한 값들을 입력받는다.

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

    cin >> N >> K;
    for (int i = 0; i < 2*N; i++) {
        cin >> wear[i];
    }
// ...

이제 코드의 핵심 부분이다. 먼저 단계를 저장할 step과 회전할 위치를 저장할 offset, 그리고 내구도가 0인 칸을 세는 wear_cnt 변수를 선언하고 초기화한다.

그런 다음 while 문으로 진입한다. 먼저 offset을 1 증가시켜 벨트가 회전하도록 한다. 또한 회전이기 때문에 (2*N)으로 모듈러 연산을 해 준다. 그런 다음 컨베이어 기준으로 N번째에 있는 로봇을 내림 처리한다.

이제 로봇의 이동을 시뮬레이션한다. 문제에서 가장 먼저 들어온 로봇부터 이동한다고 하였으므로, N-1 (코드에서는 0 based index이므로 N-2) 번째 칸부터 검사하며 이동시킨다. 만약 i번째 칸에 로봇이 없다면 이동처리도 할 수 없으므로 건너뛴다. 로봇이 있다면, 다음 칸이 비어있고, 내구도가 남아있는지 확인한 뒤 이동 처리한다.

for 문을 빠져나오면 1번째 칸의 내구도를 검사하고, 로봇을 올릴 수 있으면 로봇을 올린다.

마지막으로 while 문의 끝단에서 wear_cnt를 검사해 정지 조건인지 확인한다. 정지 조건이면 while문을 빠져나와 step을 출력하고 프로그램을 종료한다.

    int step = 0;
    int offset = 0;
    int wear_cnt = 0;
    while (true) {
        offset = (offset + 1) % (2*N);
        step++;
        belt[IDX(N-1)] = false;
        // O(N)
        for (int i = N-2; i >= 0; i--) {
            if (!belt[IDX(i)]) continue;

            if (!belt[IDX(i+1)] && wear[IDX(i+1)] >= 1) {
                belt[IDX(i)] = false;
                wear[IDX(i+1)]--;
                wear_cnt += (wear[IDX(i+1)] == 0); // 이동한 칸의 내구도가 0이면 카운터 증가
                belt[IDX(i+1)] = (i != N-2);  // 이동한 칸이 마지막이면 내림 처리
            }

        }

        if (wear[IDX(0)] >= 1) {
            belt[IDX(0)] = true;
            wear[IDX(0)]--;
            wear_cnt += (wear[IDX(0)] == 0); // 이동한 칸의 내구도가 0이면 카운터 증가
        }

        if (wear_cnt >= K) break;
    }
    cout << step << '\n';
    return 0;
}

전체 코드

#include <iostream>
using namespace std;

#define IDX(x) ((2*N - offset + x) % (2*N))

int N, K;
int wear[205];
bool belt[205];

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

    cin >> N >> K;
    for (int i = 0; i < 2*N; i++) {
        cin >> wear[i];
    }

    int step = 0;
    int offset = 0;
    int wear_cnt = 0;
    while (true) {
        offset = (offset + 1) % (2*N);
        step++;
        belt[IDX(N-1)] = false;
        // O(N)
        for (int i = N-2; i >= 0; i--) {
            if (!belt[IDX(i)]) continue;

            if (!belt[IDX(i+1)] && wear[IDX(i+1)] >= 1) {
                belt[IDX(i)] = false;
                wear[IDX(i+1)]--;
                wear_cnt += (wear[IDX(i+1)] == 0);
                belt[IDX(i+1)] = (i != N-2);
            }

        }

        if (wear[IDX(0)] >= 1) {
            belt[IDX(0)] = true;
            wear[IDX(0)]--;
            wear_cnt += (wear[IDX(0)] == 0);
        }

        if (wear_cnt >= K) break;
    }
    cout << step << '\n';
    return 0;
}

시간복잡도

내부 for 루프는 $O(N)$ 의 시간복잡도를 가지며, 전체 루프는 단계 수 $S$번 동안 반복되므로 대략 $O(NS)$ 만큼의 시간복잡도를 가진다.

각 칸이 가질 수 있는 최대 내구도는 1000이고, 각 칸은 최대 200개 존재할 수 있으므로 $S$는 최악의 경우 최대 200000번이다.

최악의 경우에도 $NS$ 는 2천만번이므로 1초($\approx$ 1억번) 시간제한을 무난하게 통과할 수 있다.