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

문제

https://www.acmicpc.net/problem/20055

풀이

≤ 써줘야 될 꺼를 ≠로 써줘서 로직 맞게 짜놓고 졸라 헤맸다;

처음에는 두 개의 덱을 이용하여 돌아가는 컨베이어 벨트의 윗면,아랫면을 표현하고 이를 이용해 로직을 구성하였다. 하지만, 연이은 시간초과가 발생하였고 다른 접근을 생각해보게 되었다.

어차피 로봇은 컨베이어 벨트의 윗면에서만 존재한다. 따라서 컨베이어 벨트의 윗면의 시작점과 끝점을 나타내는 포인터만 알고 있으면 벨트의 순환을 표현할 수 있다. 한편, 벨트 각 칸의 내구도와 로봇 존재 여부를 표현하기 위해 별도의 자료구조를 정의하였다.

이를 이용하여 모듈러 연산을 통해 벨트의 순환을 표현하고, 문제에 표현된 절차를 그대로 구현해주었다. 유의할 점은 로봇 이동 과정, 로봇 놓는 과정에서 칸의 내구도가 차감되는 부분을 잘 감안해주어야 한다는 점이었다.

로직의 시간복잡도는 로봇 이동 과정에서 가장 큰 $O(N/2)$으로 수렴하고, 이는 $N=100$인 최악의 경우에도 무난히 제한 조건 1초를 통과할 것으로 예상할 수 있다.

코드

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N, K, start, end, zeroDurationBlockCount = 0;
	static boolean[] isRobotExist;
	static List<Block> blocks = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = parseInt(st.nextToken());
		K = parseInt(st.nextToken());

		isRobotExist = new boolean[2 * N];
		start = 0;
		end = N - 1;

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int duration = parseInt(st.nextToken());
			blocks.add(new Block(i, duration));
		}

		for (int i = N; i < 2 * N; i++) {
			int duration = parseInt(st.nextToken());
			blocks.add(new Block(i, duration));
		}

		int phase = 0;
		while (zeroDurationBlockCount < K) {
			move();
			moveRobots();
			putRobot();
			phase++;
		}

		System.out.println(phase);
		br.close();
	}

	static void move() {
		start = start - 1 < 0 ? 2 * N - 1 : start - 1;
		end = end - 1 < 0 ? 2 * N - 1 : end - 1;

		isRobotExist[end] = false;
	}

	static void moveRobots() {
		int cur = end - 1 < 0 ? 2 * N - 1 : end - 1;
		int endPoint = start - 1 < 0 ? 2 * N - 1 : start - 1;

		while (cur != endPoint) {
			int next = (cur + 1) % (2 * N);
			if (!isRobotExist[cur]) {
				cur = cur - 1 < 0 ? 2 * N - 1 : cur - 1;
				continue;
			}

			Block b = blocks.get(next);
			if (isRobotExist[next] || b.duration == 0) {
				cur = cur - 1 < 0 ? 2 * N - 1 : cur - 1;
				continue;
			}

			isRobotExist[cur] = false;
			isRobotExist[next] = true;
			b.duration = Math.max(b.duration - 1, 0);
			if (b.duration == 0)
				zeroDurationBlockCount++;
		}

		isRobotExist[end] = false;
	}

	static void putRobot() {
		Block b = blocks.get(start);

		if (isRobotExist[start] || b.duration == 0)
			return;

		isRobotExist[start] = true;
		b.duration = Math.max(b.duration - 1, 0);
		if (b.duration == 0)
			zeroDurationBlockCount++;
	}

	static class Block {
		int idx, duration;

		public Block(int idx, int duration) {
			this.idx = idx;
			this.duration = duration;
		}
	}
}

결과