백준 20055_컨베이어 벨트 위의 로봇(삼성 SW 역량 테스트 기출 문제) / 난이도 : 골5

[youbeen2798]

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

문제 내용:

• 벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동
• i번 칸의 내구도는 Ai
• 1번 칸이 있는 위치를 "올리는 위치", N번 칸이 있는 위치를 "내리는 위치"
• 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내림
• 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있음
• 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소

로봇을 옮기는 과정

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동 ( 만약 이동할 수 없다면 가만히)
   (로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 함)
3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올림
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료 ( 그렇지 않다면 1번으로 다시 돌아감)

구해야 하는 출력 값

• 종료되었을 때 몇 번째 단계가 진행 중이었는지 출력 (가장 처음 수행되는 단계는 1번째 단계)

이용한 자료구조 : deque

**이 문제에서 가장 중요한 것은, deque을 이용한다는 아이디어 인 것같다..!
deque은 마지막 원소를 첫 번째 원소로 옮길 때 일정한 크기의 새로운 메모리 블록을 할당이 가능하므로, 이러한 문제를 풀 때 유용한 것같다!! 그리고, deque은 인덱스 접근이 가능하다!!

#include <iostream>
#include <deque>
using namespace std;

int n, k;
int num;

deque <int> naegu;
deque <bool> robot;


void rotate(){  	// 한 칸 회전하기	


	naegu.push_front(naegu.back());
	naegu.pop_back();

	robot.push_front(robot.back());
	robot.pop_back();
	robot[n - 1] = false; //n번칸 내리기

}

void move(){  //벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동

	for (int i = n - 2; i >= 0; i--) {
		if ((!robot[i + 1]) && (naegu[i + 1] > 0) && (robot[i])) {
			robot[i] = false;
			robot[i + 1] = true;
			naegu[i + 1]--;
		}
	}
	robot[n - 1] = false; //만약 로봇이 내리는 위치에 도착한다면

}

void  put_robot() {
	//올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
	if (!robot[0] && naegu[0] > 0) {
		robot[0] = true;
		naegu[0]--;
	}
}

int check() { //내구도가 0인 칸의 개수 세기
	int count = 0;

	for (int i = 0; i < 2 * n; i++) {
		if (naegu[i] == 0) {
			count++;
		}
	}

	return count;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int step = 1;


	cin >> n >> k;

	//내구도 입력받기
	for (int i = 0; i < 2 * n; i++) {
		cin >> num;
		naegu.push_back(num);
		robot.push_back(false);
	}


	while (true) {

		rotate();
		move();
		put_robot();

		if (check() >= k) {
			cout << step << "\n";
			break;
		}
		step++;
	}

	return 0;
}

[ghdcksgml1]

팁 하나 주자면, 덱은 무거운 자료구조라서 실행시간이 꽤 느린데

위 문제와는 다르게 인덱스에 직접 접근할 필요없고, 앞 뒤로만 접근하면 되는 문제에서는

linkedList를 쓰는게 훨씬 빠름

#include <list>

이것도 한번 공부해보셈 삼성 문제에선 쓸곳많음

[ghdcksgml1]

나처럼 pair<int,int>로 관리하는게 덜 헷갈릴듯

// 컨베이어 벨트 위의 로봇
#include <iostream>
#include <deque>

using namespace std;

int N,K;

deque<pair<int,int>> belt; //{ 내구도,로봇위치여부 }

// 벨트 한 칸 회전
void stage_1(){
  belt.push_front(belt.back());
  belt.pop_back();
  // 로봇이 내리는 위치에 있으면 내리기
  if(belt[N-1].second == 1) belt[N-1].second = 0; 
}

// 한칸 이동가능하면 이동, 아니면 가만히
// 내구도 1이상 남아있어야함.
void stage_2(){
  for(int i=N-2;i>=0;i--){
    if(belt[i].second == 1 && belt[i+1].first > 0 && belt[i+1].second == 0){
      belt[i].second = 0;
      belt[i+1].first--;
      belt[i+1].second = 1;
    }
  }
  // 로봇이 내리는 위치에 있으면 내리기
  if(belt[N-1].second == 1) belt[N-1].second = 0;
}

// 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올림
void stage_3(){
  if(belt[0].first > 0){
    belt[0].first--;
    belt[0].second = 1;
  }
}

// 내구도가 0인 칸의 개수가 K개 이상일때 과정 종료
bool stage_4(){
  int K_cnt = 0;
  for(int i=0;i<2*N;i++){
    if(belt[i].first == 0) K_cnt += 1;
  }
  if(K_cnt >= K) return true;
  else return false;
}

void init(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

int main(void){
  init();
  
  cin>>N>>K;

  for(int i=0;i<2*N;i++){
    int n;
    cin>>n;
    belt.push_back({n,0});
  }

  int cnt = 0;
  while(true){
    cnt++;
    stage_1();
    stage_2();
    stage_3();
    if(stage_4()) break;
  }
  cout<<cnt<<'\n';
}

[youbeen2798]

이렇게 하니까 덜 헷갈린다ㅎㅎ! 굳굳 고마오ㅎㅎ