[BOJ] 20055 컨테이너벨트 (c++)

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

20055번: 컨베이어 벨트 위의 로봇

 

 

시간초과는 while(zero_cnt != k) -> while(zero_cnt < k) 로 변경해주니까 해결되었다.

void solve() {
	int zero_cnt= 0;
	int robot[200*1000];
	int front = 0, back=0; 

	while(zero_cnt != k) {
		res++;
        ...

contiainer 의 내구도를 a[200] 에 저장

robot 에 각 로봇의 위치를 저장한 후 queue 의 성질과 마찬가지로 새로 들어온 robot의 index 를 back 에 저장, container 위에 있으면서 가장 오랫동안 container 에 있는 로봇의 인덱스를 front 에 저장해준다.

 

ex) N = 3

컨테이너 인덱스

0	1	2
5	4	3

robot 변화

0
front, back
1	0
front	back
2	1	0
front		back
3	2	1	0
	front		back

 

전체 코드

#include <iostream>

int n, k, res;
int a[200];

void solve() {
	int zero_cnt= 0;
	int robot[200*1000];
	int front = 0, back=0; 

	while(zero_cnt < k) {
		res++;

		// 컨테이너 회전
		int temp = a[2*n -1];
		// 끝값부터 이동
		for(int i=2*n-1; i>=1; i--) {
			a[i] = a[i-1];
		}
		a[0] = temp;

		// 로봇 회전 (queue 성질)
		for(int i=front; i<back; i++){
			++robot[i];
			if(robot[i]== n-1) {
				++front;
			}
		}

		for(int i=front; i<back; i++) {
			int next = robot[i] +1;
			if(a[next] == 0 || (i!= front && robot[i-1] == next)) 
				continue;

			robot[i] = next;
			a[next]--;
			if(robot[i] == n-1) {
				front++;
			}
			if(a[next] == 0)
				zero_cnt++;
		}

		// put new robot
		if(a[0] > 0 && (back == 0 || robot[back-1]!=0)) {
			robot[back++] = 0;
			a[0]--;
			if(a[0] == 0)
				zero_cnt++;
		}
	}
}


int main() {

	scanf("%d %d", &n, &k);

	for(int i=0; i<2*n; i++)
		scanf("%d", &a[i]);

	solve();

	printf("%d\n", res);
}