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

1. 문제 링크

문제 링크

2. 풀이

문제는 단순한 구현 문제입니다.
이 문제의 구현을 좀 더 간단히 할 수 있는 방법은 무엇이 있을까요?

컨베이어 벨트의 각 칸들은 순환합니다.
순환하는 움직임을 구현하기 좋은 자료구조는 무엇이 있을까요?
바로 큐, 덱 떠오르셔야 합니다.
근데 이 문제에서는 덱이 좀 더 사용하기 좋습니다.
덱은 시퀀스 컨테이너기 때문에 각 원소 접근이 매우 편하기 때문이고,
이 특성이 이 문제와 잘 맞아떨어집니다.

문제의 전체적인 흐름

1. 벨트를 오른쪽으로 한 칸씩 이동한 후, n번째 칸의 로봇을 내려주기
2. 로봇들을 오른쪽으로 한 칸씩 이동한 후, n번째 칸의 로봇을 내려주기
3. 1번째 칸의 로봇 올리기

이와 같은 흐름으로 정리가 가능하고
로봇을 내리는 부분은 1, 2부분에서 구현하고
내구도를 낮추는 부분은 2, 3부분에서 구현하면
문제의 조건을 충족할 수 있겠다 감이 옵니다.

0. 컨베이어 선언

deque<pair<int, int>> conveyor;

늘 말씀드리지만
어떤 자료구조를 사용하느냐에 따라 문제의 난이도는 천차만별입니다.
위에서 설명했듯이, 덱을 사용할 건데
원소는 (내구도, 로봇 존재 여부)의 정보를 가진 pair로 정의했습니다.

1. 벨트를 오른쪽으로 한 칸씩 이동한 후, n번째 칸의 로봇을 내려주기

// 1. 벨트 이동
conveyor.push_front(conveyor.back());
conveyor.pop_back();

// n번째 칸의 로봇을 내려주기
conveyor[n - 1].second = 0;

솔직히 너무 간단하죠? 직관적으로 이해되는 코드입니다.

2. 로봇들을 오른쪽으로 한 칸씩 이동한 후, n번째 칸의 로봇을 내려주기

// 2. 로봇 이동
// 먼저 올라간 로봇부터 탐색
for (int i = n - 2; i >= 0; i--) {
	// 현재 칸에 로봇이 있고, 다음 칸에 로봇이 없고 내구도가 1 이상일 때
	if (conveyor[i].second == 1 && conveyor[i + 1].second == 0 && conveyor[i + 1].first > 0) {
		conveyor[i].second = 0;
		conveyor[i + 1].second = 1;
		if (--conveyor[i + 1].first == 0) {
			k--;
		}
	}
}

// n번째 칸의 로봇을 내려주기
conveyor[n - 1].second = 0;

여기서 덱을 사용한 이유가 나오는데요,
덱은 특정 시퀀스의 원소를 조회가 가능합니다.
그렇기 때문에 위와 같은 로직 구현이 가능합니다.
먼저 올라간 로봇부터 오른쪽으로 한 칸씩 이동시켜야 하기 때문에
뒤에서부터 탐색해서 로봇이 있다면 그다음 칸으로 이동시킵니다.

3. 1번째 칸의 로봇 올리기

// n번째 칸의 로봇을 내려주기
conveyor[n - 1].second = 0;

// 3. 로봇 올리기
if (conveyor[0].first > 0 && conveyor[0].second == 0) {
	conveyor[0].second = 1;
	if (--conveyor[0].first == 0) {
		k--;
	}
}

자 이렇게 정리가 끝났습니다.
이게 한 사이클이고, 내구도가 0인 칸이 k개 이상이 되면 종료하면 됩니다.

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

int n, k;
deque<pair<int, int>> conveyor;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	for (int i = 0; i < 2 * n; i++) {
		int d;

		cin >> d;

		conveyor.push_back({ d, 0 });
	}

	int step = 0;

	while (k > 0) {
		step++;

		// 1. 벨트 이동
		conveyor.push_front(conveyor.back());
		conveyor.pop_back();

		// n번째 칸의 로봇을 내려주기
		conveyor[n - 1].second = 0;

		// 2. 로봇 이동
		// 먼저 올라간 로봇부터 탐색
		for (int i = n - 2; i >= 0; i--) {
			// 현재 칸에 로봇이 있고, 다음 칸에 로봇이 없고 내구도가 1 이상일 때
			if (conveyor[i].second == 1 && conveyor[i + 1].second == 0 && conveyor[i + 1].first > 0) {
				conveyor[i].second = 0;
				conveyor[i + 1].second = 1;
				if (--conveyor[i + 1].first == 0) {
					k--;
				}
			}
		}

		// n번째 칸의 로봇을 내려주기
		conveyor[n - 1].second = 0;

		// 3. 로봇 올리기
		if (conveyor[0].first > 0 && conveyor[0].second == 0) {
			conveyor[0].second = 1;
			if (--conveyor[0].first == 0) {
				k--;
			}
		}
	}

	cout << step;

	return 0;
}