[20055번 컨베이터 벨트 위의 로봇] - C++

statco19·2022년 2월 17일
0

알고리즘연습

목록 보기
24/27

[20055번 컨베이터 벨트 위의 로봇]
https://www.acmicpc.net/problem/20055

C++의 <algorithm> 헤더 파일에 존재하는 rotate 메서드를 사용하면 상당히 간단한 문제였다.
rotate 메서드 사용법에 대해 궁금하다면 https://www.cplusplus.com/reference/algorithm/rotate/ 링크를 참고하면 될 것 같다.

제일 처음에 로봇을 올리지 않고 컨베이어 벨트가 회전한 후, 첫 로봇을 올린다는 언급이 있었으면 고민 거리가 하나 줄었을 것 같다.

항상 내리는 위치에 로봇이 도착하면 무조건 내려줘야 한다. 즉, 컨베이어가 이동하면서 로봇이 딸려가서 내리는 위치에 도달하거나 로봇이 자체적으로 움직여서 내리는 위치에 도달할 경우, 즉시 내려줘야 한다. 그 부분만 유의한다면 상대적으로 간단한 문제였다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
// #include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 1;
int n,k;
vector<int> A;
vector<int> robots;
int start;
int finish;

void sol() {
	while(true) {
		// no robot loaded at first
		// 1.
		rotate(A.rbegin(), A.rbegin()+1, A.rend());
		rotate(robots.rbegin(), robots.rbegin()+1, robots.rend());
		if(robots[finish]) {
			robots[finish] = 0;
		}

		// 2.
		for(int i=n-2;i>=0;--i) {
			if(robots[i]) {  // start with the oldest robot
				if(!robots[i+1] && A[i+1]) {
					robots[i+1] = 1;
					robots[i] = 0;
					A[i+1]--;
				}
			}

			if(i==n-2) {
				if(robots[finish]) {
					robots[finish] = 0;
				}
			}
		}

		// 3.
		if(A[start]) {
			robots[start] = 1;
			A[start]--;
		}

		// 4.
		int cnt = 0;
		for(int i=0;i<2*n;++i) {
			if(!A[i]) {cnt++;}
		}

		if(cnt >= k) break;
		ans++;
	}

	return;
}


int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	scanf("%d%d", &n,&k);
	start = 0;
	finish = n-1;
	int num;
	for(int i=0;i<2*n;++i) {
		scanf("%d", &num);
		A.push_back(num);
		robots.push_back(0);
	}

	sol();
	
	printf("%d\n", ans);
	
	return 0;
}

실행 결과

profile
조금씩 나아지는 중입니다!

0개의 댓글