[삼성] 컨베이어벨트 위의 로봇

문제 요약

• 로봇을 옮길 컨베이어 벨트의 길이 n(컨베이어 벨트이므로 2n길이의 벨트가 돌아감)과 2n길이의 벨트에 대한 내구도가 주어집니다.
• 로봇은 컨베이어벨트의 앞에서 올라타고 끝에서 내릴 수 있습니다. 단, 컨베이어벨트의 끝에 있는 로봇은 무조건 내려야합니다.
• 내구도는 로봇이 올라타거나 옮겨갔을 때 1씩 떨어집니다.
• 내구도가 0인 칸에는 올라타거나 옮겨갈 수 없습니다.
  내구도가 0이되어 망가진 칸의 수가 k개가 될 때의 시간을 구하시오.

1초 동안 다음과 같은 일이 일어납니다.

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

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

3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

아이디어 : 시키는 대로 시뮬레이션

회전과 로봇의 움직임을 고정된 배열 안에서 shift를 사용하여 시뮬레이션

컨베이어 벨트의 길이가 100이기 때문에 해볼만 한 방법이라 생각했다.
하지만 시간초과를 받았다.
1초당 lineaer time이 걸리므로 괜찮을 거라 생각했는데 시간초과를 받아 의아했다.

시간구멍

한번의 shift마다 fill_out 함수가 호출되므로 문제가 있다.
왼쪽에서 오른쪽으로 shift대상을 바꿔가며 수행하는 함수이다.
값이 덮여씌워지는 것 때문에 아래처럼 구현을 했다.

int fill_out(int arr[], int len, int i, int val) {
	int me = arr[i];
	arr[i] = val;
	return me;
}
void rot(int arr[], int len) {
	int val = arr[0];
	for (int i = 1; i < 2 * n; i++) {
		val = fill_out(arr,len,i, val);
	}
	arr[0] = val;
}

시간구멍을 매꾸기

뒤에서부터 shift대상을 바꿔가며 수행하면 값이 덮일 걱정이 없다.

void rot() {
	int temp = belt[2 * N - 1];
	for (int i = 2 * N - 1; i >= 1; i--)
		belt[i] = belt[i - 1];
	belt[0] = temp;

	for (int i = N - 1; i >= 1; i--)
		check[i] = check[i - 1];
	check[0] = 0;
}

정답 코드

이렇게 시뮬레이션 하는 방법이 아래 두번째 방법보다 더 빠르다(40ms)

#include <iostream>
using namespace std;

int N, K;
int belt[200];
int check[100];

void rot() {
	int temp = belt[2 * N - 1];
	for (int i = 2 * N - 1; i >= 1; i--)
		belt[i] = belt[i - 1];
	belt[0] = temp;

	for (int i = N - 1; i >= 1; i--)
		check[i] = check[i - 1];
	check[0] = 0;
}
void move() {
	check[N - 1] = 0;
	for (int i = N - 2; i >= 0; i--) {
		if (check[i] == 0)
			continue;

		if (check[i + 1] == 0 && belt[i + 1] > 0) {
			check[i] = 0;
			check[i + 1] = 1;
			belt[i + 1] -= 1;
		}
	}
}
void put() {
	if (belt[0] > 0) {
		belt[0]--;
		check[0] = 1;
	}
}

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

	int t = 0;
	while (true) {
		rot();
		move();
		put();
		t++;

		int cnt = 0;
		for (int i = 0; i < 2 * N; i++)
			if (belt[i] == 0)
				cnt++;

		if (cnt >= K)
			break;
	}
	cout << t;
	return 0;
}

회전을 고정된 배열 안에서 rollable하게 관찰+ 로봇은 따로 관리

1초당 linear하게 동작했을 때 시간초과가 걸리니까 shift에 대해 rollable개념을 도입해서, 2*n길이 배열 중 신경 써야할 윗부분을 관리했다.

s와 e 변수를 통해 신경쓸 윗부분 관리

void rot(queue<int> &q) {
	if (s == 0) {
		s = 2 * n - 1;
	}
	else {
		s--;
	}
    //내려야할 곳에 로봇이 있다면 하차
	int e = (s + n - 1) % (2 * n);
	if (ronb[e] == 1) {
		ronb[e] = 0;
		q.pop();
	}
}

또한 모든 로봇이 한 칸씩 움직일 때 linear time이 발생하지 않도록 queue와 queue와 동일한 내용의 벨트위 상황을 보여주는 배열을 사용해 로봇을 관리했고, 1초당 O(현재 올라가있는 로봇 수)만큼만 비용이 발생한다. 하지만 위 방법보다 자료구조를 사용하기 때문에 실제 시간은 90ms로 더 느렸다.

#include<iostream>
#include<queue>
using namespace std;
int n, k;
int belt[200];
int ronb[200];
queue<int> r;
int sum_d = 0;
int s = 0;

void rot(queue<int> &q) {
	if (s == 0) {
		s = 2 * n - 1;
	}
	else {
		s--;
	}
	int e = (s + n - 1) % (2 * n);
	if (ronb[e] == 1) {
		ronb[e] = 0;
		q.pop();
	}
}
void lower_belt(int i) {
	belt[i]--;
	if (belt[i] == 0) {
		sum_d++;
	}
}

queue<int> move_robot(queue<int> q) {
	int e = (s + n - 1) % (2 * n);
	queue<int> newq;
	while (!q.empty()) {
		int robot = q.front();
		q.pop();
		int next = (robot + 1) % (2 * n);
		if (belt[next] >0&&ronb[next] == 0) {
			ronb[robot] = 0;
			ronb[next] = 1;
			lower_belt(next);
			if (next == e) {
				ronb[next] = 0;
			}
			else {
				newq.push(next);
			}
		}
		else {
			newq.push(robot);
		}

	}
	return newq;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < 2 * n; i++) {
		cin >> belt[i];
	}
	queue<int> q;
	int time = 1;
	while (true) {
		rot(q);
		q = move_robot(q);
		if (ronb[s] == 0&& belt[s]>0) {
			q.push(s);
			ronb[s] = 1;
			lower_belt(s);
		}
		if (sum_d >= k) {
			break;
		}
		time++;
	}
	cout << time << endl;
}

미래의 나에게

1. 빅O 표기법으로 같은 시간이 걸리더라도 자료구조를 쓰는 것보다 배열을 한칸씩 도는 게 더 빠르다.
2. 함수호출이 작은 연산 하나마다 생기는 코드는 좋지 않다.
3. ~~에 도달했을 때 즉시 어케 된다란 조건이 있으면 매 움직임마다 검사하자.