문제

BOJ 20055: 컨베이어 벨트 위의 로봇 https://www.acmicpc.net/problem/20055

풀이

조건

• 로봇은 올리는 위치(belt[0])에만 올릴 수 있다. 언제든지 로봇이 내리는 위치(belt[N-1])에 도달하면 그 즉시 내린다.
• 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다. 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다.
• 아래와 같은 일이 순서대로 일어난다.
  1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
  2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
     • 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
  3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
  4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
• 종료되었을 때 몇 번째 단계가 진행 중이었는지 구한다. 가장 처음 수행되는 단계는 1번째 단계이다.

풀이 순서

• 단계를 끝낼 수 있는지 확인한다.
• 벨트를 1칸 회전한다.
• 벨트 위에 있는 로봇도 다음 칸으로 이동시킨다.
  • 이동 시켰을 때 출구 칸에 온 로봇은 즉시 제거한다.
• 로봇이 다음 칸으로 이동할 수 있는지 확인한다.
  • 현재 칸에 로봇이 있고 && 다음 칸에 로봇이 없고 && 다음 칸의 내구도가 0보다 크다면
  • 벨트 위의 로봇이 스스로 다음 칸으로 이동한다.
  • 다음 칸으로 이동하면 해당 칸의 내구도를 -1 한다.
• 입구 칸에 로봇을 새로 올린다.
  • 입구 칸의 내구도를 -1 한다.

코드

import java.util.*;
import java.io.*;

public class Main {
    
	static int N, K;
	
	static int[] belt;
	static boolean[] robot;
	
	static int phase;
	
    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];
    	robot = new boolean[N]; // 로봇은 윗 줄에만 있음
    	
    	// 벨트의 내구도를 배열에 넣음
    	st = new StringTokenizer(br.readLine(), " ");
    	for(int i=0; i<belt.length; i++) {
    		belt[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	phase = 0; // 출력할 단계
    	while(!isEnd()) {
    		// 벨트 1칸 회전
    		int temp = belt[belt.length - 1];
    		for(int i=belt.length - 1; i>0; i--) {
    			belt[i] = belt[i-1];
    		}
    		belt[0] = temp;
    		
    		// 벨트 위에 있는 로봇도 1칸 이동
    		for(int i=robot.length - 1; i>0; i--) {
    			robot[i] = robot[i-1];
    		}
    		robot[0] = false; // 입구 칸에 있떤 로봇은 다음 칸으로 이동했음
    		robot[N-1] = false; // 출구 칸에 있는 로봇은 제거
    		
    		// 로봇 1칸 갈 수 있으면 이동
    		for(int i=N-1; i>0; i--) {
    			// 이동할 로봇이 있으면 && 다음 칸에 로봇이 없으면 && 다음 칸의 내구도가 0보다 크면
    			if(robot[i-1] && !robot[i] && belt[i]>0) {
    				robot[i] = true;
    				robot[i-1] = false;
    				belt[i]--;
    			}
    		}	
    		
    		// 입구에 로봇 새로 올림
    		if(belt[0] > 0) {
    			robot[0] = true;
    			belt[0]--;
    		}
    		
    		// 단계 +1
    		phase++;
    	}
    	
    	System.out.println(phase);
    }
    
    // 단계를 끝낼 수 있으면 true 반환
    static boolean isEnd() {
    	int cnt = 0;
    	
    	for(int i=0; i<2*N; i++) {
    		if(belt[i] <= 0) {
    			cnt++;
    		}
    		// 내구도가 0 이하인 벨트가 K개 이상이면 true
    		if(cnt >= K) {
    			return true;
    		}
    	}
    	
    	return false;
    }
    
}

정리

• 벨트의 회전, 칸의 내구도, 로봇의 이동 등의 정보를 구현하는 데 너무 복잡하게 해서 시간이 오래걸렸었다.
• 벨트 위에 있는 로봇을 1칸 이동시킬 때 출구 칸에 있는 로봇을 제거하는 것을 빼먹어서 시간 낭비를 했다.