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

문제 링크입니다. https://www.acmicpc.net/problem/20055

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

생각보다 간단한 구현 문제입니다.

 

문제를 풀기 위해선 구현해야할 것이 3개 있습니다.

1. 컨베이어 벨트 움직이기

2. 로봇 움직이기

3. 로봇 놓기

 

먼저 컨베이어 벨트는 2줄로 되어있지만, 실제로 로봇이 올라가고 내려가는 부분은 1과 N부분 입니다. 따라서 2차원 배열을 통해 벨트를 관리할 필요는 없으며, N*2개의 1차원 배열을 이용하면 됩니다.

 

1. 컨베이어 벨트 움직이기

 

컨베이어 벨트는 한칸씩 회전합니다. 한칸씩 움직이면서 시작점과 끝점도 움직입니다.

예를 들어 처음, 시작점과 끝점이 (1,3)이지만, 한칸 움직인 뒤에는 (6,2)가 됩니다.

이와 같이 한칸 움직일 때마다 1씩 감소하지만, 0이 된다면 N*2의 값을 가지는 것을 알 수 있습니다. 

 

2. 로봇 움직이기

 

컨베이어 벨트를 움직였으니 이번에는 로봇을 움직일 차례입니다.

로봇을 움직이려면 다음 칸에 다른 로봇이 있는지를 알아야합니다.

따라서 check 배열을 하나 만들어 X번째 칸에 로봇이 있는지의 여부를 저장했습니다.

로봇은 한칸씩 앞으로 가기에 현재 칸에서 +1을 해주면 되지만, 해당 값이 N*2를 넘을 경우 1로 만들어 주면 됩니다.

로봇이 갈 수 있는 경우는 다음에 이동할 곳에 로봇이 없으며 && 다음 벨트의 내구도가 1 이상인 경우입니다.

해당 경우를 만족한다면 현재 칸의 로봇을 지워주고 다음 칸으로 이동해줍니다.

 

여기서 유의할 점이 두가지가 있습니다.

1. 먼저 올라간 로봇부터 움직이기에 queue를 사용하지만, 벨트 위의 로봇 갯수만 움직여 Size를 따로 받고 반복한다.

2. 이동한 곳이 End라면 바로 로봇을 빼준다.

이 두가지만 유의하면 쉽게 구현할 수 있습니다.

 

3. 로봇 놓기

 

로봇은 시작점에만 놓을 수 있습니다. 따라서 Start 지점을 확인하는데

이때도 Start지점의 벨트 내구도가 1이상이며 로봇이 없는 경우에만 놓습니다.

 

 

자세한 것은 코드를 참고해주세요 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>

using namespace std;

queue<int> robot;
int check[202];
int belt_life[202];
int N, K;
int Start, End, life_zero;

void move_belt() {
	Start--;
	End--;
	if (Start == 0) Start = N * 2;
	if (End == 0) End = N * 2;
}

void move_robot() {
	int Size = robot.size();
	for (int i = 1; i <= Size; i++) {
		int Robot = robot.front();
		robot.pop();
		if (Robot == End) {
			check[Robot] = 0;
			continue;
		}
		int next_belt = Robot + 1;
		if (next_belt > 2 * N) next_belt = 1;
		if (belt_life[next_belt] >= 1 && check[next_belt] == 0) {
			belt_life[next_belt]--;
			if (belt_life[next_belt] == 0) life_zero++;
			check[Robot] = 0;
			if (next_belt == End) continue;
			check[next_belt] = 1;
			robot.push(next_belt);
		}
		else robot.push(Robot);
	}
}

void put_robot() {
	if (check[Start] == 0 && belt_life[Start] >= 1) {
		check[Start] = 1;
		belt_life[Start]--;
		robot.push(Start);
		if (belt_life[Start] == 0) life_zero++;
	}
}

void solve() {
	int ans = 0;
	Start = 1, End = N;
	while (1) {
		if (life_zero >= K) break;
		ans++;
		move_belt();
		move_robot();
		put_robot();
		
	}
	cout << ans;
}


int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N * 2; i++) {
		cin >> belt_life[i];
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요