문제
첫인상
문제가 잘 이해되지 않았던 문제.
'건너편' 이 뭘 의미하는지 명확하게 제시되어 있으면 더 좋았을 것 같다.
질문 검색에 들어가니 문제 이해에 어려움을 겪는 사람이 나뿐만이 아니었던 것 같다.
제시된 그림과 내 머리속의 컨베이어 벨트의 개념, 건너편으로 로봇 이동시키는 게 뭘 의미하는지 등의 정보를 조합해서 문제의 의도를 파악하는 게 어려웠다.
그 외엔 하나하나 제시된 조건에 따라 구현하면 된다.
문제 접근
문제 흐름
- 컨베이어 벨트가 움직인다.
- 로봇이 움직인다.
- 로봇이 새로 추가된다.
로봇이 컨베이어 벨트를 밟을 때마다 컨베이어 벨트의 내구도는 1씩 감소하며, 로봇은 내구도가 0인 컨베이어 벨트에 올라갈 수 없다.
내구도가 0인 컨베이어 벨트의 개수가 K개가 될 때까지 위 과정을 반복하도록 구현하면 되는 시뮬레이션 문제이다.
관건0. 움직이는 컨베이어 벨트
구현: move_belt()
컨베이어 벨트가 움직일 때는 위에 위치한 로봇도 함께 움직인다.
배열 내의 원소를 이동시킬 때 인덱스에 주의해서 구현하면 된다.
로봇의 유무를 나타내는 is_robot 배열과 컨베이어 벨트의 내구도를 나타내는 Map 배열을 함께 움직여주었다.
컨베이어 벨트가 움직인 후 로봇이 N의 위치에 도달하게 되면 로봇은 컨베이어 벨트를 통해 건너편으로 간 것이 되므로 (문제에서 말하는 내리는 위치의 의미) 이에 따라 is_robot 배열에서 로봇을 제거해줘야 한다.
관건1. 로봇의 이동
구현: move_robot()
is_robot 배열을 끝부터 순회하며(가장 먼저 벨트 위에 올라온 로봇부터 움직여야 하므로) (1) 현재 위치에 로봇이 있고 (2) 다음 위치에 로봇이 없고 (3) 다음 위치의 컨베이어 벨트의 내구도가 0 이상일 경우 로봇을 움직이도록 했다. 이때 로봇이 이동하면 이동한 곳의 내구도는 1 감소한다.
관건2. 새로운 로봇
구현: add_robot()
로봇은 새로 추가될 수 있는 위치가 정해져 있으므로 is_robot 배열의 인덱스 1을 확인하면 된다.
자료구조
이 문제는 배열을 이용해서 풀 수 있는 문제다.
'가장 먼저 컨베이어 벨트에 위치한 로봇' 이라는 문구에 꽂혀 벡터를 사용했다가 시간초과에서 헤어나오지 못하다 벡터 대신 배열을 사용해서 문제를 풀 수 있었다. 그러고 보니 문제를 다 푸는 데 주어진 시간이 1초였다.
로봇이 계속해서 추가될 경우 벡터에서 순회해야 하는 원소의 개수가 늘어나기 때문에 시간 복잡도가 증가한 것으로 파악된다.
풀이
#include <iostream>
#include <cstring>
using namespace std;
int N, K, rst;
int Map[201];
int is_robot[101];
void input() {
cin >> N >> K;
for (int i = 1; i <= 2 * N; i++) {
cin >> Map[i];
}
memset(is_robot, 0, sizeof(is_robot));
}
void move_belt() {
int temp = Map[2 * N];
for (int i = 2 * N; i >= 2; i--) {
Map[i] = Map[i - 1];
}
Map[1] = temp;
for (int i = N; i >= 2; i--) {
is_robot[i] = is_robot[i - 1];
}
is_robot[1] = 0;
if (is_robot[N]) is_robot[N] = 0;
}
void move_robot() {
for (int i = N - 1; i >= 1; i--) {
if (is_robot[i] && !is_robot[i + 1] && Map[i + 1] > 0) {
Map[i + 1] -= 1;
is_robot[i] = 0;
is_robot[i + 1] = 1;
if (i + 1 == N) {
is_robot[i + 1] = 0;
}
}
}
}
void add_robot() {
if (!is_robot[1] && Map[1] > 0) {
Map[1] -= 1;
is_robot[1] = 1;
}
}
int is_finish() {
int cnt = 0;
for (int i = 1; i <= 2 * N; i++) {
if (Map[i] == 0) cnt++;
}
return cnt >= K;
}
void solve() {
int cnt = 0;
while (true) {
cnt++;
move_belt();
move_robot();
add_robot();
if (is_finish()) break;
}
rst = cnt;
}
int main() {
input();
solve();
cout << rst << endl;
}