[JAVA] 백준 20055 컨베이어 벨트 위의 로봇

오늘의 문제 : https://www.acmicpc.net/problem/20055

 

조건을 확실하게 정리하는 습관을 기릅시다. 왜 와이? 요번문제에서 바로 코딩 들어가서 삽질을 좀 했기 때문이죠.

 

투 포인터 및 구현문제입니다.

 

1. 작업의 순서  

  1) 벨트가 돌아간다.

    로봇이 끝부분에 도달하는 즉시 벨트에서 나온다. 

    시작점과 끝점을 -1 시켜 벨트의 회전을 구현. 

  2) 로봇이 이동한다.

  3) 로봇이 추가된다.

    현재 추가할 경로의 내구도가 0인 경우 패스.

    현재 추가할 경로에 로봇이 이미 있다면 패스. 

 

2. 로봇의 이동 상황 구분.

  1) 이동할 로봇이 이미 끝부분에 있는 경우

    즉. 시 제외.

  2) 이동할 로봇의 다음경로에 이미 로봇이 있는 경우

    원래 위치 그대로 추가.

  3) 이동할 로봇의 경로의 내구도가 0인 경우.

    원래 위치 그대로 추가. 

  3) 이동할 로봇의 경로가 끝부분인 경우

    벨트의 내구도를 감소하고 즉시 제외.

  4) 로봇이 정상적으로 이동한 경우

    벨트의 내구도를 감소하고, 로봇을 추가. 

 

코드

public class Num20055_컨벤이어벨트위의로봇 {
    static int n,k,startPoint,endPoint,zeroBelt;
    static int[] belt;
    static Deque<Integer> que;
    static boolean[] isRobot;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        belt = new int[2*n];
        isRobot = new boolean[2*n];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<2*n;i++){
            belt[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 1;
        startPoint = 0;
        endPoint = n-1;
        zeroBelt = 0;
        que = new LinkedList<>();
        while(true){
            rolling();
            if(robotMoving())break;
            if(addRobot())break;
            answer++;
        }
        System.out.println(answer);
    }
    public static void rolling(){
        startPoint --;
        endPoint --;
        if(startPoint <0){
            startPoint += 2*n;
        }
        if(endPoint <0){
            endPoint += 2*n;
        }
    }
    public static boolean robotMoving(){
        int size = que.size();
        for(int i=0;i<size;i++){
            int tmp = que.pollFirst();
            if(tmp == endPoint) {
                isRobot[tmp] = false;
                continue;
            }
            if(tmp+1>= 2*n) {
                if(belt[tmp+1-2*n]==0 || isRobot[tmp+1-2*n]){
                    que.addLast(tmp);
                    continue;
                }
                if(tmp+1-2*n!=endPoint) {
                    isRobot[tmp+1-2*n] = true;
                    que.addLast(tmp+1-2*n);
                }
                isRobot[tmp] = false;
                belt[tmp+1-2*n] --;
                if(belt[tmp+1-2*n] == 0) zeroBelt++;
                if(zeroBelt==k) return true;
            }else{
                if(belt[tmp+1]==0 || isRobot[tmp+1]){
                    que.addLast(tmp);
                    continue;
                }
                if(tmp+1 != endPoint){
                    isRobot[tmp+1] = true;
                    que.addLast(tmp+1);
                }
                isRobot[tmp] = false;
                belt[tmp+1] --;
                if(belt[tmp+1] == 0) zeroBelt++;
                if(zeroBelt==k) return true;
            }
        }
        return false;
    }
    public static boolean addRobot(){
        if(belt[startPoint] >0 && !isRobot[startPoint]){
            belt[startPoint] --;
            if(belt[startPoint] == 0) zeroBelt++;
            isRobot[startPoint] = true;
            que.add(startPoint);
        }
        return zeroBelt == k;
    }
}

 

후기

 

엄슴