[C] 컨베이어 벨트 위의 로봇

백준 20055번

 

실버 수준인 만큼 문제에서 하라는대로만 하면 어려운 반례 없이 바로 맞출 수 있었다

생각해보니까 solved ac 난이도 끄고 풀어야겠다 앞으로

 

아무튼 삼성 기출이라고 해도 단순 구현이 가능한지 먼저 시간복잡도를 대충 확인해보았다

벨트 회전을 하나하나 다 해준다해도 최대 200개 이고 내구도도 1000까지밖에 없어서 단순 구현도 무리가 없어 보였다

 

이번에도 디버깅 과정이 포함된 코드를 올려보았다

벨트 돌리는 것을 가장 먼저 구현했는데 뒤에서부터 한칸씩 땡겨줬다

그리고 가장 앞에 있는 로봇이 N번째 위치라면 로봇을 벨트 위에서 내리고

가장 앞에 있는 로봇의 위치를 다시 찾아주었다

 

벨트가 다 돌아갔으면 이제 로봇들이 움직일 차례이다

가장 앞에 있는 로봇부터 이동가능한 경우 한칸씩 이동시켜주었다

이때도 로봇이 이동해서 N번째 위치로 갔다면 로봇을 벨트 위에서 내려주었다

벨트 위에서 내릴 수 있는 곳이 두개 있어서 내리는 것은 처음부터 함수화시켜서 사용했다

 

마지막으로 1번 위치에 로봇이 없고 내구성이 남아있다면 새 로봇을 올려주었다

이 때 해당 로봇이 벨트 위의 유일한 로봇이 된다면 가장 앞에 있는 로봇이라고 체크해주었다

 

위의 과정을 반복하면서 내구도가 0인 칸의 개수가 K개를 넘는다면 즉시 종료시키고 몇단계까지 진행했는지 출력해주었다

 

#include <stdio.h>
 
int belt[205];
int robot[205];
int N,K,cnt=0;
int first=0;
 
// 벨트가 한 칸 회전 시 N
// 로봇 이동 N
// 내구도 최대 1000
// 1000 * 100 = 100000
 
void printBelt(){
    for(int i = 1; i <= N ; i++) printf("%d ",belt[i]);
    printf("\n");
    for(int i = 2*N ; i>N ; i--) printf("%d ",belt[i]);
    printf("\n\n");
}
 
void printRobot(){
    for(int i = 1; i <= N ; i++) printf("%d ",robot[i]);
    printf("\n");
    for(int i = 2*N ; i>N ; i--) printf("%d ",robot[i]);
    printf("\n\n");
}
 
void robotOff(){
    robot[N] = 0;
    for(int i = N ; i >= 1 ; i--){
        if(robot[i]){
            first = i;
            return;
        }
    }
 
    // no lobot left
    first = 0;
}
 
int main(){
    scanf("%d %d",&N,&K);
    for(int i = 1 ; i <= 2*N ; i++) {
        scanf("%d",&belt[i]);
        if(belt[i]==0) cnt++;
    }
    int step = 1;
    while(1){
        //printf("step : %d\n",step);
        // 벨트가 한 칸 회전
        int belt_back = belt[2*N];
        int robot_back = robot[2*N];
        if(robot[first]) first++;
        for(int i = 2*N ; i >= 2 ; i--){
            belt[i] = belt[i-1];
            robot[i] = robot[i-1];
        }
        belt[1] = belt_back;
        robot[1] = robot_back;
        if(first==N) robotOff();
        // printBelt();
        // printRobot();
 
        // 가장 먼저 벨트에 올라간 로봇부터 이동
        //printf("Robot move\n");
        for(int i = first; i >=1 ; i--){
            if(robot[i] && !robot[i+1] && belt[i+1]){
                if(i==first) first++;
                robot[i] = 0;
                robot[i+1] = 1;
                belt[i+1]--;
                if(belt[i+1]==0) cnt++;
            }
        }
        if(first==N) robotOff();
        // printBelt();
        // printRobot();
        //printf("First %d\n",first);
        if(!robot[1] && belt[1]){
            //printf("New robot\n");
            robot[1] = 1;
            belt[1]--;
            if(belt[1]==0) cnt++;
            if(first==0) first=1;
            // printBelt();
            // printRobot();
        }
        if(cnt>=K) break;
        step++;
    }
    printf("%d\n",step);
}