컨베이어벨트 위에 로봇을 올리는 위치와 로봇을 내리는 위치가 정해져있다. 또한 컨베이어벨트의 내구도도 설정이 되어있어 내구도가 있는 컨베이어벨트의 위치만 사용할 수 있다.
이 때 컨베이어벨트를 작동시켜 일을 하다가 종료되었을 때 몇 단계가 진행중이었는지 출력하는 프로그램 작성.
- 종료조건 : 컨베이어벨트의 내구도가 0인 칸의 개수가 K 개 이상인 경우
[ 입력 ]
- 첫째 줄에 컨베이어벨트의 길이 ( N ), 종료개수 K 입력
- 둘째 줄에 공백을 사이에 두고 각 컨베이어벨트의 내구도를 입력받음.
[ 출력 ]
- 컨베이어벨트의 K개의 위치에서 내구도가 0이 되어 작동을 멈췄을 때 진행중이던 단계 출력.
이번 문제는 알고리즘 분류에서도 보다시피 "simulation" 문제이다.
simulation 문제는 해결해야하는 문제에서 주어진 과정들을 따라 수행한 후 나오는 결과를 구하면 되는 유형의 문제이다.
이번 문제에서 주어진 과정은 아래와 같다.
즉, 위에 보이는 과정들을 종료조건을 만날때까지 수행하면서 결과를 도출하면 되는 문제이다.
나는 이 문제를 풀면서 총 4 가지의 step 을 각각 함수로 구현해주었다.
그리고 함수 구현 이전에 컨베이어벨트의 내구도가 저장되어있는 deque 하나, 컨베이어벨트 위에 로봇이 있는지 확인하는 bool deque 하나를 선언해 준 후 함수를 구현해주었다.
step1. 컨베이어벨트 회전 ( void rotate() )
회전하면 변경되는 정보는 다음과 같다.
- 내구도 : 0 -> 1 -> . . . -> 2N-1 -> 2N 으로 내구도 회전
- 로봇 존재 여부 : 0 -> 1 -> . . . -> 2N-1 -> 2N 으로 회전
이렇게 컨베이어벨트를 회전시키기 위해 앞뒤로 원소를 삽입할 수 있는 deque 자료구조를 사용했다.
deque 를 사용하면 가장 뒤에 있는 원소를 앞에 삽입하면 회전되는 효과를 얻을 수 있다.
그리고 이때 로봇이 무조건 내리는 위치인 N번째 (index로 하면 N-1번째) 위치는 언제나 로봇이 내려질테니 false 로 설정.
step2. 벨트가 움직이는 방향으로 로봇 이동
- N번째 위치에서는 무조건 로봇이 내려질테니 이동을 고려할 로봇이 없음.
=> 즉, 1번째 ~ N-1번째 위치에 대해서만 고려해주면 됨.- 이동조건은 다음과 같다.
- 이동하려는 칸에 로봇 존재 X
- 이동하려는 칸에 내구도 1 이상 남아있어야 함.
- 내가 현재 관심있는 위치에 로봇이 있어야 함.
- 이 때도 step1 과 같이 N번째는 언제나 로봇이 내려오기 때문에 false 로 설정
step3. 벨트 위에 로봇 올리기
- 로봇을 올릴 수 있는 조건
- 올리는 위치의 칸의 내구도가 0 이상
- 올리는 위치에 로봇이 없어야 함.
step4. 내구도가 0인 칸의 개수 확인 ( 종료조건 확인하기 위함. )
- 컨베이어벨트의 내구도를 확인하면서 0이면 count 증가시킨 후 최종 count 를 return
이렇게 문제에서 주어진 각각의 과정들을 함수로 구현한 후, main 문에서 종료조건을 만날때까지 step1 ~ step4 까지 반복해준 횟수를 출력해주면 문제 해결!
#include <iostream>
#include <deque>
using namespace std;
// 전역변수 설정 (N : 컨베이어벨트 길이, K : 내구도가 0인 칸의 최대 개수)
int N = 0, K = 0;
// 컨베이어벨트 내구도 관리 공간
deque<int> hp;
// 컨베이어벨트위에 물건 존재여부 관리
deque<bool> conv;
// step1. 벨트 회전 (로봇과 함께)
// deque 를 사용하다 보니 deque 의 가장 마지막 원소를 가장 앞에 push 하면 회전이 됨.
void rotate() {
// 내구도를 회전
hp.push_front(hp.back());
hp.pop_back();
// 물건 존재여부역시 함께 회전
conv.push_front(conv.back());
conv.pop_back();
// 내리는 위치인 N-1 위치는 언제나 로봇이 도착하면 바로 내리니 false 설정
conv[N-1] = false;
}
// step2. 로봇 이동 (벨트가 움직이는 방향으로)
// N번째 위치에서는 무조건 로봇이 내려질테니 1번째 ~ N-1번째에 대해서만 로봇을 움직여주면 됨.
void move_robot() {
for(int i = N-2; i >= 0; i--) {
// 이동 조건 : 이동하려는 칸에 로봇 존재 x && 이동하려는 칸의 내구도 1 이상 && 현재 i 위치에 로봇이 있으면
if((conv[i+1] == false) && (hp[i+1] > 0) && (conv[i] == true)) {
conv[i+1] = true;
conv[i] = false;
hp[i+1] --;
}
// 이동할 수 없다면 현재 위치의 가만히 있으므로 변화 X
// N번째 위치에 로봇이 도달했다면 바로 내려줘야하므로 N번째 위치의 conv 는 언제나 false
conv[N-1] = false;
}
}
// step3. 벨트 위에 로봇 올리기 (올리는 위치의 칸이 내구도가 0이 아니면)
void put_robot() {
// 올리는 위치의 칸의 내구도가 0이 아니고 && 로봇이 없다면 로봇 올림 (내구도 1 감소)
if((conv[0] == false) && (hp[0] > 0)) {
conv[0] = true;
hp[0] --;
}
}
// step4. 내구도가 0인 칸의 개수 확인 (return : 내구도가 0인 칸의 개수)
int check() {
int count = 0;
for(int i = 0; i < 2*N; i++) {
if(hp[i] == 0) {
count ++;
}
}
return count;
}
int main() {
// 컨베이어벨트 길이 N 과 종료조건 K 입력
cin >> N >> K;
// A1 ~ A2n 까지 입력
for(int i = 0; i < 2*N; i++) {
int input = 0;
cin >> input;
// 컨베이어벨트 내구도 관리 queue 에 저장
hp.push_back(input);
// 아직 로봇이 없으니 컨베이어벨트 위치에 false 로 저장
conv.push_back(false);
}
// 현재 몇단계 수행중인지 저장하는 변수 선언
int step = 1;
// 종료조건과 일치하기 전까지 step1 ~ 4 까지 반복수행한다.
while(true) {
// step 1 ~ 4 수행
rotate();
move_robot();
put_robot();
// 종료조건 : 내구도가 0인 칸의 개수가 K 개 이상
int count = check();
if(count >= K) {
cout << step << endl;
return 0;
}
// 종료조건에 걸리지 않으면 단계를 올리고 step 1 다시 진행
step++;
}
return 0;
}