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

문제 : https://www.acmicpc.net/problem/20055

 

 

[ 문제 요약 ]

• 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있습니다.
• 벨트는 길이 1간격으로 2N 개의 칸으로 나누어져 있습니다.
• 벨트 한 칸 회전 시 1부터 2N-1번까지의 칸은 다음 번호 칸 위치로 이동하고, 2N 번 칸은 1번 위치로 이동합니다.
• i 번 칸의 내구도는 Ai입니다. 1번 칸 위치를 올리는 위치, N 번 칸 위치를 내리는 위치라 합니다. 컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려 합니다. 로봇은 올리는 위치에만 올릴 수 있습니다.
• 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내립니다. 로봇은 스스로 이동할 수 있고 로봇을 올리는 위치에 올릴 때와 로봇이 이동할 때 그 칸의 내구도는 즉시 1만큼 감소합니다. 컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려 합니다. 아래와 같은 일이 순서대로 일어납니다.

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동 가능하면 이동, 이동 불가 시 가만히 있음( 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상일 때만 가능)
3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올림
4. 내구도가 0인 칸의 개수가 K 이상이면 과정 종료, 아니면 1번으로 돌아가 재반복

• 종료되었을 때의 단계를 출력합니다. 첫 단계는 1번째 단계입니다.

 

[ 테스트 케이스 설명 ]

4 5 // 칸 개수(2<=100), 0인 칸의 개수(1<=2N)
10 1 10 6 3 4 8 2// 각 칸의 내구도(1<=1,000 / 칸의 개수 * 2만큼 주어짐 )
답 : 24

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

 

지문에 주어진 4가지 스탭이 하나의 세트입니다.

문제 요구사항 대로 먼저 로봇과 컨베이어 벨트를 회전시키고, 첫 번째 인덱스에 로봇을 올릴 수 있다면 올려주면 됩니다.

 

[ 정답 코드 ]

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

class Main{
	
	static int N;
	static int zeroCnt;
	static int[] arr;
	static boolean[] isRobot;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 칸 개수(2<=100)
		zeroCnt = Integer.parseInt(st.nextToken());// 0인 칸의 개수(1<=2N)
		arr = new int[N<<1];
		isRobot = new boolean[N<<1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<arr.length; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		int step = 0;
		
		while(zeroCnt>0)
		{
			++step;
			
			rotate();
			moveRobots();
			loadRobot();
			
		}
		System.out.print(step);
	}
	static void rotate() {
		int last = arr[arr.length - 1];
		
		for(int i=arr.length - 1; i>0; i--)
		{
			arr[i] = arr[i - 1];
			isRobot[i] = isRobot[i - 1];
		}
		
		arr[0] = last;
		isRobot[0] = false;
		isRobot[N - 1] = false;
	}
	static void moveRobots() {
		for(int n=N-1; n>0; n--)
		{
			// 이동하려는 곳에 로봇이 없고, 내구도가 1이상이며, 현재 위치에 로봇이 있다면 로봇이동 
			if(!isRobot[n] && isRobot[n-1] && arr[n] > 0)
			{
				isRobot[n] = true;
				isRobot[n - 1] = false;
				arr[n]--;
				
				if(arr[n] == 0) --zeroCnt;
			}
		}
		
		isRobot[N - 1] = false; // N번째 위치의 로봇 내림
	}
	static void loadRobot() {
		if(arr[0] > 0)// 0번 인덱스에 내구도가 1이상이면
		{
			isRobot[0] = true;// 로봇을 올림
			arr[0]--;
			
			if(arr[0]==0) --zeroCnt;
		}
	}
}