BOJ[20055]. 컨베이어 벨트 위의 로봇

문제를 잘 이해해야 한다.

 

 

우선 내구도가 떨어지는 경우는 두 가지다.
1) 로봇이 어떤 칸으로 올라갈 때, 올라가려는 칸의 내구도가 감소한다.

2) 로봇이 어떤 칸으로 이동할 때, 이동하려는 칸의 내구도가 감소한다.

 

로봇을 옮기는 과정은 다음과 같다1) 벨트가 회전한다 rotate()2) 가장 먼저 올라와있던 로봇부터(가장 먼저 올라온 로봇이 아님) 벨트가 회전하는 방향으로 한 칸 이동한다. move()    이때 이동하기 위해서는 이동하려는 칸에 로봇이 없고, 내구도 >= 13) 올라가는 위치(컨베이어 벨트의 처음)에 로봇이 없으면 로봇을 올린다 put_robot()4) 내구도가 0인 칸의 개수가 k개 이상이라면 과정을 종료한다. 그렇지 않다면 1)번으로 돌아간다.

 

// 20055 컨베이어 벨트 위의 로봇
// https://www.acmicpc.net/problem/20055

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

# include <stdio.h>
# include <iostream>
# include <deque>
using namespace std;

int n = 0, k = 0, step = 0, cnt = 0;
deque <int> belt;
deque<bool> robot;

void rotation() {
	belt.push_front(belt.back());
	belt.pop_back();

	robot.push_front(robot.back());
	robot.pop_back();
}

void move() {
	for (int i = n-2; i >= 0; i--){
		if(robot[i] && !robot[i+1] && belt[i+1] >= 1){
			robot[i] = false;
			robot[i+1] = true;
			belt[i + 1]--;
		}
	}
}

void put_robot() {
	if(belt[0]>0) {
		belt[0]--;		robot[0]=true;
	}	
}

int get_zero_cnt(){
	int zero = 0;
	for (int i = 0; i < 2*n; i++){
		if(belt[i]==0)
			zero++;
	}
	return zero;
}

int main(void){
	cin >> n >> k;

	for (int i = 0; i < 2 * n; i++){
		int val;
		cin >> val;
		belt.push_back(val);
		robot.push_back(false);
	}
	while(true){
		step += 1;
		rotation();
		robot[n - 1] = false;
		move();
		robot[n - 1] = false;
		put_robot();
		if(get_zero_cnt() >= k){
			cout << step << "\n";
			return 0;
		}
	}
	return 0;
}

원래는 que를 사용했는데 먼저 올라와 있던 로봇을 먼저 옮겨야 하는 걸 알게 되고나서 deque로 변경하였다.

참고한 블로그가 있는데 너무 설명이 잘 되어있어서 감사하게 공부했다!

deque 아이디어만 얻고 혼자 짜보고 확인했는데 나름 내 코드로 체화된 것 같아서 기쁘다!!

ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-20055%EB%B2%88-%EC%BB%A8%EB%B2%A0%EC%9D%B4%EC%96%B4-%EB%B2%A8%ED%8A%B8-%EC%9C%84%EC%9D%98-%EB%A1%9C%EB%B4%87-%EC%82%BC%EC%84%B1-%EA%B8%B0%EC%B6%9C