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

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

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

 

- 시간복잡도는, 칸과 로봇을 옮기는 작업 O(N) + 내구도가 로봇이 올려질때마다 반드시 깎이므로 O(2NA)해서 O(2NA)이다. 

 

- 칸의 개수와 로봇의 개수를 배열에 담고, while문 조건으로 매 단계마다 내구도가 0인 칸의 개수가 k 이상인지를 확인한다. 가장 먼저 로봇과 벨트를 한 칸씩 이동시키고, 로봇이 내리는 칸에 도달했으면 로봇을 내려준다. 이동 과정에서 첫 칸을 최신화하는 로직을 빼 먹으면 안 된다.

다음으로, 로봇이 앞으로 이동 가능하다면 이동시킨다. 이 때, 내구도가 0이라면 zero_square++ 해 준다.

마지막으로, 올리는 칸에 내구도가 있다면 로봇을 올려주고, 이 때도 해당 칸의 내구도가 0인지 체크를 한다.

 

- 삼성 코테 기출문제중에 가장 쉬운 문제라 생각한다. 이런 문제만 나오면 얼마나 좋을까

 

#include <iostream>
using namespace std;
int n, k;
int square[201]; // 해당 칸의 내구도
int robot[101]; //칸 위의 로봇. 로봇이 존재하면 1, 아니면 0
int zero_square; // 내구도가 0인 칸의 개수
int answer; // 총 단계 수
int main() {
	cin >> n >> k;
	for (int i = 1; i <= 2 * n; i++) {
		cin >> square[i];
	}
	while (zero_square<k) {
		answer++;
		//로봇과 벨트 한 칸씩 앞으로 이동
		for (int i = n-1; i >= 1; i--) {
			robot[i + 1] = robot[i];
		}
		robot[1] = 0;
		if (robot[n]) robot[n] = 0;
		int temp_square = square[2 * n];
		for (int i = 2 * n - 1; i >= 1; i--) {
			square[i + 1] = square[i];
		}
		square[1] = temp_square;
		//로봇 한 칸씩 앞으로 이동, 이동시 내구도 감소
		for (int i = n - 1; i >= 1; i--) {
			if (robot[i]) {
				if (!robot[i + 1] && square[i + 1]) {
					robot[i + 1] = 1;
					robot[i] = 0;
					square[i + 1]--;
					if (!square[i + 1]) zero_square++;
				}
			}
		}
		if (robot[n]) robot[n] = 0;
		// 올리는 칸이 0이 아니면 로봇 올리기
		if (square[1]) {
			robot[1] = 1;
			square[1]--;
			if (!square[1]) zero_square++;
		}
	}
	cout << answer;
	return 0;
}