[C++] 백준 20055번 컨베이어 벨트 위의 로봇

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

삼성 SW 역량 테스트 기출 문제

 

에 수록되어 있는 문제중 하나.

실버1 문제이고, 정답률이 높길래 풀어봤는데, 문제가 상당히 표현이 애매모호하게 되어있다.

게시판을 참조해서 사람들이 해석해준 방법을 보고난 후에 풀 수 있었다.

 

문제풀이

문제의 조건을 정리하면 다음과 같다.

• 컨베이어 벨트는 2층구조이고, 1층은 1 ~ N, 2층은 N + 1 ~ 2N의 범위이다. (2층은 2N ~ N + 1이라고 생각해야한다.)
• 각 컨베이어 벨트 칸 하나마다 로봇을 하나씩만 올릴 수 있다. 로봇이 내리는 위치(N)에 도달하면 그 즉시 내리면 된다. 또한 로봇은 컨베이어 벨트에서 스스로 이동할 수 있다.
• 로봇이 이동하거나, 올려질 경우에는 해당 칸의 내구도는 1이상이여야 하고, 해당 칸에는 로봇이 존재해선 안된다.
• 가장 중요한 조건은 컨베이어 벨트의 목적은 로봇을 반대편으로 옮기는 것이다. 즉, 반대편으로 로봇이 한 번 이동하면, 로봇은 컨베이어 벨트 바깥으로 간다는 것이다. 

문제를 아무리 읽어도, 위 조건을 유추할 수 없었다. (로봇을 한 번 올리면 계속 올려져 있을텐데, 로봇을 올린다는 것은 무슨 말이지? 로봇을 올릴 때는 중복해서 올릴 수 있는건가? 근데 한 칸마다 하나의 로봇만 가능한데,)

결국, 게시판에서 사람들이 올린 글들을 보고나서야 위 조건을 유추할 수 있었다.

• 로봇을 건너편으로 옮기는 과정에서 다음과 같은 일이 순서대로 일어난다.

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

 

종료되었을 때, 몇 번째 단계인지 출력하는게 문제이다.

밑줄 친 굵은 줄만 해석이 가능했다면 어렵지 않게 풀 수 있다.

 

#include <iostream>
using namespace std;

int beltLength, maxZeroCnt;
int remainDurability[3][101]; // 1 : 위(->), 2 : 아래(<-)
bool isOnRobot[101]; // 로봇이 반대편에서는 이동하지 않음.
int zeroCnt, ans;

사용한 STL과 변수

 

• beltLength, maxZeroCnt : 입력받는 N, K이다.
• remainDurability 배열 : 현재 컨베이어벨트의 남은 내구도를 기록하는 배열이다.
• isOnRobot 배열 : 현재 1층 컨베이어벨트에 로봇이 존재하는지를 기록하는 배열이다. 2층은 고려하지 않아도 된다.
• zeroCnt, ans : zeroCnt는 현재 내구도가 0개인 칸의 개수, ans는 문제의 출력이다.

 

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> beltLength >> maxZeroCnt;

	for (int i = 1; i <= beltLength; i++) {
		cin >> remainDurability[1][i];
	}

	for (int i = beltLength; i >= 1; i--) {
		cin >> remainDurability[2][i];
	}

	go(1);

	cout << ans;

	return 0;
}

메인함수.

처음에 N, K를 입력받는다.

그리고 컨베이어 벨트의 1층은 1 ~ N으로 입력받고, 2층은 2N ~ N + 1이므로 위처럼 입력받으면 된다.

 

그리고 go() 메서드를 호출한다 매개변수 1은 1단계임을 나타낸다. 자세한 설명은 뒤에 나온다.

go() 메서드가 종료되면 ans를 출력한다.

 

void go(int idx) {
	//1. 회전
	spinBelt();

	//2. 벨트 회전 방향으로 로봇이동
	moveRobot();

	//3. 로봇 올리기
	if (remainDurability[1][1] > 0) {
		remainDurability[1][1]--;
		isOnRobot[1] = true;
	}

	//4. 내구도 0칸 K개 이상 체크
	zeroCnt = 0;
	for (int i = 1; i <= beltLength; i++) {
		if (remainDurability[1][i] == 0) { zeroCnt++; }
		if (remainDurability[2][i] == 0) { zeroCnt++; }
	}

	if (zeroCnt >= maxZeroCnt) { ans = idx; return; }
	else { go(idx + 1); }
}

컨베이어 벨트 및 로봇 이동 메서드.

문제의 조건에 맞게 4단계로 나누어서 구현했다.

1. 컨베이어 벨트 회전

2. 이동할 수 있는 로봇 이동

3. 첫번째 칸에 로봇 올릴 수 있다면 로봇 올림.

4. 내구도 0인 칸 몇 개인지 세고, K개 이상이면 Return. 아니라면 다시 한 번 go()메서드 호출

 

이제 1, 2번 메서드를 살펴보자.

void spinBelt() {
	int prevDurability = remainDurability[1][1];
	int prevRobotCheck = isOnRobot[1];
	for (int i = 2; i <= beltLength; i++) {
		int tmp = remainDurability[1][i];
		int tmpRobot = isOnRobot[i];

		remainDurability[1][i] = prevDurability;
		isOnRobot[i] = prevRobotCheck;

		prevDurability = tmp;
		prevRobotCheck = tmpRobot;

		if (i == beltLength && isOnRobot[i]) {ㅌ
			//N번째에서는 로봇 내림(사라짐.)
			isOnRobot[i] = false;
		}
	}

	//2번째라인은 로봇은 필요없다.
	for (int i = beltLength; i >= 1; i--) {
		int tmp = remainDurability[2][i];
		remainDurability[2][i] = prevDurability;
		prevDurability = tmp;
	}

	remainDurability[1][1] = prevDurability;
	isOnRobot[1] = false;
}

컨베이어 벨트 회전 메서드

 

컨베이어 벨트의 1층은 로봇도 이동시켜주어야 한다.

1층의 2번째 idx부터 시작하며, 바로 이전 칸의 로봇의 존재 유무와 내구도를 저장해뒀다가 현재 칸에 기록한다.

만일 N번째 칸의 기록을 끝냈는데 현재 칸에 로봇이 있다면 로봇을 내린다.

(건너편으로 내림을 뜻함. N + 1로 가는게 아님)

 

그리고 2층은 문제에서 표현하는 N + 1부터 시작하며 1층과 마찬가지로 바로 이전의 내구도를 저장해뒀다가 현재 칸에 기록한다. 2층에서는 로봇이 존재하지 않으므로 내구도만 움직여주면된다.

 

마지막으로 1층 첫번째 칸에 문제에서 표현하는 2N번째 칸의 내구도를 넣어주면 된다.

회전할 경우, 첫번째 칸은 무조건 로봇이 존재하지 않게되므로 false로 만들어주었다.

 

void moveRobot() {
	for (int i = beltLength - 1; i >= 1; i--) {
		int nxtIdx = i + 1;
		if (isOnRobot[i] && remainDurability[1][nxtIdx] > 0 && !isOnRobot[nxtIdx]) {
			isOnRobot[i] = false;
			remainDurability[1][nxtIdx]--;
			isOnRobot[nxtIdx] = true;

			if (nxtIdx == beltLength && isOnRobot[nxtIdx]) {
				isOnRobot[nxtIdx] = false;
			}
		}
	}
}

로봇 이동 메서드.

 

처음에 for문의 시작을 1부터 했는데 이렇게 할 경우, 끝에서부터 이동하면 이동가능한데 이동을 하지 않는 경우가 발생할 수 있다.

ex.) 컨베이어 벨트에 [ 0 1 1 0 ]이 있다고 생각해보자.

이 경우 끝에서부터 이동하면 [ 0 0 1 0](마지막 칸 로봇 내림)이 되는데 앞에서부터 이동시키면 [ 0 1 0 0]이 된다.

문제의 조건에도 가장 먼저 벨트에 올라간 로봇부터 이동하라고 했으므로 끝에서부터 이동시켜주면 된다.

 

끝 칸부터 다음 칸에 이동할 수 있는지 확인하며 이동시킬 수 있는 로봇들을 이동시켜준다.

 

만일 N번째 칸에 로봇이 왔을 경우, 해당 칸에 로봇을 반대편으로 보낸다.(제거한다.)

 

문제를 처음보면 이게 무슨 문제인가 싶었다. 사실 이문제를 풀려고 한 게 오늘이 처음은 아니지만

처음 봤을때는 진짜 무슨 말인지 몰랐었다. 삼성 기출문제이기 때문에 크게 할 말은 없다...ㅠ

질문 게시판이 없었다면 솔직히 못 풀었을 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.