[BOJ] 20055. 컨베이어 벨트 위의 로봇 - Java

📝 문제

문제 | 백준 20055. 컨베이어 벨트 위의 로봇

💡 풀이 과정

문제를 이해하는 데에 가장 시간을 많이 썼던 문제였다..

처음엔 두 줄의 컨테이너 벨트가 같은 높이에 있는 상태로 이해했기 때문에, 로봇이 올라가고 내려가는 동작을 완전히 잘못 이해했었다. 즉, 문제에 있는 컨베이어 벨트 그림이 컨베이어 벨트를 위에서 바라본 상태인 줄 착각한 것이다. 이 부분 때문에 한참을 헤메다가 컨베이어 벨트 두 줄이 상/하로 나뉘어 있음을 이해하고 난 후에는 금방 구현할 수 있었다.

구현은 문제 조건에 충실하게 구현하면 되는 문제로, 구현의 난이도는 크게 높지 않았다. 처음엔 컨베이어 벨트의 처음과 마지막 양쪽에서 요소를 추가/삭제해야 하기 때문에 덱(Deque)을 사용하려고 했었다. 다만 매번 내구도가 0인 벨트 개수를 세야 하고, 벨트가 이동한 후에는 로봇이 추가적으로 이동을 하기 때문에 모든 요소를 탐색해야 하는 경우가 발생한다. 이런 경우에는 덱이나 연결리스트 등을 사용하면 오히려 인덱스 기반 검색으로 인해 성능이 저하될 수 있다.

문제에서는 컨베이어 벨트를 두 줄로 표현하고 있지만, 사실상 하나로 이어져있기 때문에 2N 길이의 일차원 배열을 이용해서 구현할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int N,K;
	
	static int[] A;
	
	static boolean[] belt;
	
	static boolean check() { //내구도가 0인 칸 세기
		int cnt=0;
		for(int i: A) {
			if(i==0) cnt++;
			
			if(cnt>=K) return false;
		}
		
		return true;
	}
	
	static int move() {
		int step = 0;
		
		while(check()) {
			
			step++;
			
			//1번: 벨트 회전
			int temp = A[2*N-1]; //마지막꺼
			for(int i=2*N-1;i>0;i--)
				A[i] = A[i-1];
			A[0] = temp;	
			
			for(int i=N-1;i>0;i--) {
				belt[i] = belt[i-1];
			}
			
			belt[0] = false;
			belt[N-1] = false;
			
			//2번: 로봇 이동
			for(int i=N-1;i>0;i--) {
				if(!belt[i-1] || belt[i] || A[i]<1) continue;
				A[i]--;
				belt[i] = true;
				belt[i-1] = false;
			}
			
			//3번: 올리기
			if(A[0]<=0) continue;
			belt[0] = true;
			A[0]--;
		}
		
		return step;
	}
	
	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());
		
		A = new int[2*N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0,size=2*N;i<size;i++) {
			A[i] = Integer.parseInt(st.nextToken());
		} //end input
		
		belt = new boolean[N];
		
		System.out.println(move());
	}
}