컨베이어 벨트 위의 로봇 (20055)
1. 문제 링크
2. 풀이
문제는 단순한 구현 문제입니다.
이 문제의 구현을 좀 더 간단히 할 수 있는 방법은 무엇이 있을까요?
컨베이어 벨트의 각 칸들은 순환합니다.
순환하는 움직임을 구현하기 좋은 자료구조는 무엇이 있을까요?
바로 큐, 덱 떠오르셔야 합니다.
근데 이 문제에서는 덱이 좀 더 사용하기 좋습니다.
덱은 시퀀스 컨테이너기 때문에 각 원소 접근이 매우 편하기 때문이고,
이 특성이 이 문제와 잘 맞아떨어집니다.
문제의 전체적인 흐름
- 벨트를 오른쪽으로 한 칸씩 이동한 후,
n
번째 칸의 로봇을 내려주기 - 로봇들을 오른쪽으로 한 칸씩 이동한 후,
n
번째 칸의 로봇을 내려주기 1
번째 칸의 로봇 올리기
이와 같은 흐름으로 정리가 가능하고
로봇을 내리는 부분은 1, 2
부분에서 구현하고
내구도를 낮추는 부분은 2, 3
부분에서 구현하면
문제의 조건을 충족할 수 있겠다 감이 옵니다.
0. 컨베이어 선언
deque<pair<int, int>> conveyor;
늘 말씀드리지만
어떤 자료구조를 사용하느냐에 따라 문제의 난이도는 천차만별입니다.
위에서 설명했듯이, 덱을 사용할 건데
원소는 (내구도, 로봇 존재 여부)
의 정보를 가진 pair
로 정의했습니다.
1. 벨트를 오른쪽으로 한 칸씩 이동한 후, n
번째 칸의 로봇을 내려주기
// 1. 벨트 이동
conveyor.push_front(conveyor.back());
conveyor.pop_back();
// n번째 칸의 로봇을 내려주기
conveyor[n - 1].second = 0;
솔직히 너무 간단하죠? 직관적으로 이해되는 코드입니다.
2. 로봇들을 오른쪽으로 한 칸씩 이동한 후, n
번째 칸의 로봇을 내려주기
// 2. 로봇 이동
// 먼저 올라간 로봇부터 탐색
for (int i = n - 2; i >= 0; i--) {
// 현재 칸에 로봇이 있고, 다음 칸에 로봇이 없고 내구도가 1 이상일 때
if (conveyor[i].second == 1 && conveyor[i + 1].second == 0 && conveyor[i + 1].first > 0) {
conveyor[i].second = 0;
conveyor[i + 1].second = 1;
if (--conveyor[i + 1].first == 0) {
k--;
}
}
}
// n번째 칸의 로봇을 내려주기
conveyor[n - 1].second = 0;
여기서 덱을 사용한 이유가 나오는데요,
덱은 특정 시퀀스의 원소를 조회가 가능합니다.
그렇기 때문에 위와 같은 로직 구현이 가능합니다.
먼저 올라간 로봇부터 오른쪽으로 한 칸씩 이동시켜야 하기 때문에
뒤에서부터 탐색해서 로봇이 있다면 그다음 칸으로 이동시킵니다.
3. 1
번째 칸의 로봇 올리기
// n번째 칸의 로봇을 내려주기
conveyor[n - 1].second = 0;
// 3. 로봇 올리기
if (conveyor[0].first > 0 && conveyor[0].second == 0) {
conveyor[0].second = 1;
if (--conveyor[0].first == 0) {
k--;
}
}
자 이렇게 정리가 끝났습니다.
이게 한 사이클이고, 내구도가 0인 칸이 k
개 이상이 되면 종료하면 됩니다.
3. 전체 코드
#include <bits/stdc++.h>
using namespace std;
int n, k;
deque<pair<int, int>> conveyor;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 0; i < 2 * n; i++) {
int d;
cin >> d;
conveyor.push_back({ d, 0 });
}
int step = 0;
while (k > 0) {
step++;
// 1. 벨트 이동
conveyor.push_front(conveyor.back());
conveyor.pop_back();
// n번째 칸의 로봇을 내려주기
conveyor[n - 1].second = 0;
// 2. 로봇 이동
// 먼저 올라간 로봇부터 탐색
for (int i = n - 2; i >= 0; i--) {
// 현재 칸에 로봇이 있고, 다음 칸에 로봇이 없고 내구도가 1 이상일 때
if (conveyor[i].second == 1 && conveyor[i + 1].second == 0 && conveyor[i + 1].first > 0) {
conveyor[i].second = 0;
conveyor[i + 1].second = 1;
if (--conveyor[i + 1].first == 0) {
k--;
}
}
}
// n번째 칸의 로봇을 내려주기
conveyor[n - 1].second = 0;
// 3. 로봇 올리기
if (conveyor[0].first > 0 && conveyor[0].second == 0) {
conveyor[0].second = 1;
if (--conveyor[0].first == 0) {
k--;
}
}
}
cout << step;
return 0;
}
Author And Source
이 문제에 관하여(컨베이어 벨트 위의 로봇 (20055)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@front/백준-컨베이어-벨트-위의-로봇-20055저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)