[Algorithm][C++] BOJ 20055 컨베이어 벨트 위의 로봇

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

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

 

na982님 풀이 참고

https://na982.tistory.com/131

[삼성 SW 역량 테스트] 컨베이어 벨트 위의 로봇

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int n, k;
int map[200];

int solve() {
	int ret = 0, zero_cnt = 0;
	int robot[200 * 1000];
	int fr = 0, re = 0;

	while (zero_cnt < k) {
		++ret;

		int temp = map[2 * n - 1];
		for (int i = 2*n - 1; i > 0; i--) {
			map[i] = map[i - 1];
		}
		map[0] = temp;
		for (int i = fr; i < re; i++) {
			robot[i]++;
			if (robot[i] == n - 1) {
				fr++;
			}
		}
		for (int i = fr; i < re; i++) {
			int next = robot[i] + 1;
			if (map[next] == 0 || (i != fr && robot[i - 1] == next)) continue;
			robot[i] = next;
			if (robot[i] == n - 1) ++fr;
			--map[next];
			if (map[next] == 0) zero_cnt++;
		}
		if (map[0] > 0 && (re == 0 || robot[re - 1] != 0)) {
			robot[re++] = 0;
			--map[0];
			if (map[0] == 0) zero_cnt++;
		}
	}
	return ret;
}

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 0; i < 2*n; i++) {
		scanf("%d", &map[i]);
	}
	int ans = solve();
	printf("%d", ans);
	return 0;
}