📜 문제
시뮬레이션 문제로 처음에 어떤 자료구조를 이용해서 문제의 상황을 구현할지 고민 하다가 vector를 이용했다.
📖 풀이
- 공간복잡도
1) 컨베이어 벨트 각 칸의 내구도를 저장할 vector
2) 컨베이어 벨트 각 칸의 박스 로봇 유무를 저장할 vector
1), 2) 둘을 pair 로 묶어서 하나의 vector 로 저장했다.
최악의 경우 N=100 이므로, 해당 문제에서 메모리 초과를 걱정할 필요는 없을 것 같다.
- 시간복잡도
1) 컨베이어 벨트가 회전하는 과정
O(2*N)
2) 로봇이 컨베이어 벨트 방향으로 회전하는 과정O(N)
3) 종료조건을 판단하는 과정O(N)
🖥 코드
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
vector<pair<int,bool>>c; //해당 벨트의 내구도, 로봇의 유무
int n, k, down_pos, up_pos, answer=1;
//종료조건 판단
bool isover(){
int cnt=0;
for(int i=0; i<2*n; i++){
if(c[i].first==0)cnt++;
}
if(cnt>=k)return true;
else return false;
}
//컨베이어 회전 구현
void rotate_c(){
pair<int,bool>temp=c[2*n-1];
c.pop_back();
c.insert(c.begin(),temp);
if(c[down_pos].second==true)c[down_pos].second=false;
}
//로보트 회전 구현 + 회전 후 올리는 위치에 로보트 올리기
void rotate_r(){
for(int i=n-2; i>=0; i--){
if(c[i].second==true){
//컨베이어 회전 방향으로 로보트가 존재하지 않고,내구도가 0보다 큰 경우 이동
if(c[i+1].first>=1 && !c[i+1].second){
c[i+1].first-=1;
c[i+1].second=1;
c[i].second=0;
//만약 로보트가 이동한 위치가 내리는 위치면 바로 내려준다.
if(i+1==down_pos){
c[down_pos].second=false;
}
}
}
}
//올리는 위치의 내구도가 0이 아니면 로보트 올리기
if(c[up_pos].first>=1){
c[up_pos].first-=1;
c[up_pos].second=1;
}
}
//문제의 과정 그대로
void func(){
while(1){
rotate_c();
rotate_r();
if(isover())break;
answer++;
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=0; i<2*n; i++){
int num;
cin>>num;
c.push_back({num,0});
}
//올리는 위치, 내리는 위치의 인덱스 설정
up_pos=0;
down_pos=n-1;
func();
cout<<answer;
return 0;
}🔨 피드백
처음 문제를 읽고 이해하는데 시간이 조금 걸렸던것 같다.
- 컨베이어 벨트 회전
- 로보트 옮기기
이렇게 크게 2가지 과정으로 나눠서 생각할 수 있다.
첫번째 과정에서 컨베이어 벨트를 구현하기 위해 덱이나 연결 리스트를 이용하면 O(1)으로 구현할 수 있지만 c++ vector를 이용해 O(N) 의 시간복잡도가 발생하더라도 시간초과가 나지 않을거라 생각해 vector를 이용해 구현했다.
두번째 과정에서 로봇을 옮길때는 해당 조건을 주의해서 구현했다.
벨트에 가장 먼저 올라간 로봇부터 회전 방향으로 이동한다.
문제의 조건에서 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다 라는 조건이 있기 때문에 벨트에 가장 먼저 올라간 로봇은 N번 벨트에서 부터 1번 벨트 순서로 확인하면서 로봇이 있는지 확인하면 되는 것이 보장된다.
문제의 조건 그대로를 구현만 하면 크게 어려운 부분없이 해결할 수 있는 문제였다. 문제를 읽고 빨리 이해할 수 있도록 연습!🔥
