백준 20055번 - 컨베이어 벨트 위의 로봇

www.acmicpc.net/problem/20055

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

 

2020 하반기 삼성 SW 역량테스트 문제 중 하나였어요.

 

생각보다 쉬웠다는 후기가 많아서 겁도 없이 미팅 때 라이브로 풀다가.. 

 

디버깅을 거의 30분 넘게 했는데도 잘못된 점을 찾지 못했어요ㅠㅠ..

 

그래서 너무 이상해서 질문 검색 게시판에 들어가보니 <문제에서 놓치기 쉬운 것들> 이란 글이 보이더라구요..

 

궁금하시면 한번 확인해보세요! 

 

저는 저 글을 보고 책상을 뿌실뻔 했어요!

 

제가 미팅 때 문제를 리뷰하면서 설명했던 부분이 완전히 잘못 이해했다는 것을 지금 알았기에 다시 적어보면

 

1. 1번째 칸에는 로봇을 올리고, N번째 칸에서는 로봇을 땅에 내린다.

 

이 뜻을 제가 완전히 잘못 이해했었는데, 저는 컨베이어 벨트가 위, 아래로 이어져 있어서 땅에 내린다는 게 컨베이어 벨트 아래쪽으로 내린다는 의미로 생각했었는데 지금 생각해보니 말도 안 되는 거였네요ㅠㅠ

 

어쨌든 이 조건을 통해 우리가 추리해내야 하는 것은

 

반드시 모든 로봇은 위쪽 컨베이어 벨트에서만 놀겠구나! 정도일 것 같네요.

 

2. 규칙에 따라 이동한다.

 

규칙은 문제에서 읽어보면 되고

 

중요한 점은 컨베이어 벨트 회전 -> 로봇 이동 -> 로봇 올리기 순서이므로

 

여기서 얻을 수 있는 것은

 

컨베이어 벨트 회전 시에는 내구도가 깎이지 않는다! 이 정도 일 것 같네요.

 

 

자 이제 실제 구현해 대해 생각해볼게요.

 

먼저 이어져있는 컨베이어 벨트를 구현해야 하는데

 

그림을 그려서 생각해보면 컨베이어 벨트의 이동은 배열 하나로 표현할 수 있어요!

 

ex) N -> N+1 즉 아래로 내려가는 것은 결국 다음 index로 이동하는 것과 마찬가지!

 

이때 주의할 점은 마지막 칸과 첫 번째 칸이 이어져 있다는 점!

 

그럼 보통 처음 생각하기에는

"아.. 귀찮네 이거 한 칸 이동시키려면 전부 오른쪽으로 한 칸씩 옮겨야 되자나"

"모든 배열의 원소를 움직이는 것도 귀찮은데 시간 복잡도가 괜찮을라나?"

 

다들 이런 생각 하셨을 거예요ㅎㅎ (저도 처음엔 그랬어요)

 

근데!

 

미팅 때 설명드렸듯이 C++ STL의 deque를 사용하면 O(1) 시간에 코드 두 줄로 이동이 가능하답니다!

 

#include <deque>

deque<int> belt;
// 벨트를 채워 넣었다고 가정해보면
belt.push_front(belt.back());
belt.pop_back();

belt란 deque가 1 2 3 4 5 6으로 채워져 있다고 가정해보면,

 

belt의 마지막인 6을 belt의 앞부분에 삽입하고, -> 6 1 2 3 4 5 6

 

belt에서 pop_back()을 하면 -> 6 1 2 3 4 5

 

짜잔! 

belt를 한 칸씩 회전시켰어요! 단 두줄만에!

 

이제 회전을 시켰으니 로봇을 이동시켜야 돼요.

 

저는 로봇의 위치를 담는 bool 형 배열 'check'를 선언했어요!

 

쉽게 말해서 check[index] = true 라면 index 번째 칸에는 로봇이 들어있다는 거에요.

 

로봇을 이동시키는 것도 아주 간단해요.

 

아까 위에서 구했듯이 로봇은 반드시 위에 컨베이어 벨트에만 존재할 수 있으므로

 

for (int i = n - 2; i >= 0; i--) { // 어차피 먼저 벨트에 올라갔으면 맨 앞쪽에 있겠지
	if (check[i] == true && dq[i + 1] >= 1 && check[i + 1] == false) {// i번째에 로봇이 있다면, i+1 번째 내구도가 남아있다면
		dq[i + 1]--; // i+1번째로 옮길 것임 -> 즉 내구도 깎임
		check[i] = false; // 갱신
		if (i == n - 2) continue; // i+1 == n-1, 로봇을 땅에 내려야 함
		check[i + 1] = true;
		}
	}

 

n번째(i=n-1이겠죠? 배열은 0부터 시작하니까) 칸에는 어떤 경우든 로봇이 있을 수 없어요!

 

그렇기 때문에 for (int i = n - 2; i >= 0; i--) 요 부분만 이동시켜주면 됩니다!

 

이동시킨다 = 내구도를 깎는다 이기 때문에

 

조건만 잘 신경 써준다면 어렵지 않게 구현할 수 있을 겁니다!

 

이렇게 로봇을 이동시켜주었다면 이제 로봇을 올려야겠죠?

 

로봇을 올리는 건 진짜 제일 쉬워요 진짜루

 

// 3. 로봇 올리기
// 로봇이 올라갈 수 있는 조건 : 0번 칸에 내구도가 1 이상, 로봇이 없어야 함
if (dq[0] >= 1 && check[0] == false) {
	check[0] = true;
	dq[0]--;
}

 

내구도가 남아있다면 올려주면 될 겁니다! 당연히 로봇의 위치도 갱신해주고요!

 

이제 정말 다했어요..

 

이제 종료 조건만 정리하면 되는데

 

종료 조건도 매우 간단해요. 내구도가 0인 칸이 몇 개인지만 알면 됩니다.

 

뭐.. 사실 시간 복잡도를 아낄 수 있는 여러 방법이 있지만

 

저는 굉장히 지쳤고 피곤하기 때문에 O(2N) 만에 구하는 브루트포스 방법으로 구현했어요.

 

// 컨베이어 벨트의 내구도 측정 -> 0이 몇 개 인지 반환
int find() {
	int ret = 0;
	for (int i = 0; i < dq.size(); i++) {
		if (dq[i] == 0) ret++;
	}
	return ret;
}

그냥 전부 돌면서 확인하는 코드입니다.

 

브루트포스 배웠으니까 다 알겠죠?

 

 

자! 이제 이 코드들을 싸악 다 합치면 끝이에요!

 

자세한 내용들은 코드에 주석으로 달아놓았으니 꼭 확인해보세요!

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;

int n, k, x;
deque <bool> check; // 로봇이 있는지 없는지를 판단
deque <int> dq; // 내구도가 저장된 덱
int ans = 0;

// 컨베이어 벨트의 내구도 측정 -> 0이 몇 개 인지 반환
int find() {
	int ret = 0;
	for (int i = 0; i < dq.size(); i++) {
		if (dq[i] == 0) ret++;
	}
	return ret;
}

void simul() {
	while (1) {
		if (find() >= k) break;
		ans++;
		// 1. 벨트 회전
		dq.push_front(dq.back());
		dq.pop_back();
		// 벨트가 회전하면 위의 로봇들도 회전해야 함
		check.push_front(check.back());
		check.pop_back();
		if (check[n - 1] == true) check[n - 1] = false; // N번째 위치라면 로봇을 땅에 내림
		// 2. 가장 먼저 벨트에 올라간 로봇부터 회전하는 방향으로 한칸 이동
		// 로봇은 반드시 위 컨베이어 벨트에만 있을 것이다. (N 번째에 무조건 내리니까)
		for (int i = n - 2; i >= 0; i--) { // 어차피 먼저 벨트에 올라갔으면 맨 앞쪽에 있겠지
			if (check[i] == true && dq[i + 1] >= 1 && check[i + 1] == false) {// i번째에 로봇이 있다면, i+1 번째 내구도가 남아있다면
				dq[i + 1]--; // i+1번째로 옮길 것임 -> 즉 내구도 깎임
				check[i] = false; // 갱신
				if (i == n - 2) continue; // i+1 == n-1, 로봇을 땅에 내려야 함
				check[i + 1] = true;
			}
		}
		// 3. 로봇 올리기
		// 로봇이 올라갈 수 있는 조건 : 0번 칸에 내구도가 1 이상, 로봇이 없어야 함
		if (dq[0] >= 1 && check[0] == false) {
			check[0] = true;
			dq[0]--;
		}
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < 2 * n; i++) {
		cin >> x;
		dq.push_back(x);
		check.push_back(false);
	}
	simul();
	cout << ans << "\n";
}

 

코드를 잘 보면 주석을 빼고 나면 사실 몇 줄 안 되는 코드였어요ㅠㅠ

 

사실 여기까지 보면 그렇게 어려운 문제는 아니었던 것 같아요... (제가 할 말은 아니지만..)

 

혹시 저만 문제를 잘못 이해한 건가요.. 

 

어쨌든 이렇게 해서 해결해 보았고 생각보다 엄청 괜찮은 문제였네요!

 

다들 고생하셨고 목요일에 봐요~