[백준] 20055. 컨베이어 벨트 위의 로봇 - 실버1

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

20055번: 컨베이어 벨트 위의 로봇

 

문제 요약

길이가 2N인 벨트가 컨베이어 벨트를 위아래로 감싸며 돌고 있다.

1번 칸이 있는 위치는 "올리는 위치", N번 칸이 있는 위치는 "내리는 위치"이다.

 

컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올리는 위치에만 올릴 수 있고, 내리는 위치에 도달하면 그 즉시 내린다. 로봇을 올리는 위치에 올리거나 어떤 칸으로 이동하면 내구도는 1만큼 감소한다.

 

로봇을 옮기는 과정은 다음과 같다.

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
   1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.

 

 

문제 해결 아이디어

전형적인 시뮬레이션 문제다. belt와 robot 배열을 두어 인덱스를 맞추면서 현재 로봇이 어느 벨트에 있는지 확인해 준다. robot 배열은 로봇이 있으면 true, 없으면 false인 배열이고, belt는 내구도가 들어 있다. cnt 변수를 두어 K보다 작을 동안 반복문을 돌려 주며 로봇을 이동시킨다. off() 함수를 두어 로봇이 내리는 위치가 되진 않았는지 단계마다 체크해 준다. 내구도가 0이 되면 cnt 변수를 하나 증가시킨다.

 

 

완성된 코드

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

public class Main_BOJ_20055_컨베이어벨트위의로봇 {
	static int N;
	static int K;
	static int[] belt;
	static boolean[] robot; // 로봇 위치를 체크하는 배열. true면 현재 칸에 로봇이 있다는 뜻.

	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());
		K = Integer.parseInt(st.nextToken());

		// 1. 벨트 회전
		// 2. 로봇이 이동할 수 있다면 (이동하려는 칸에 로봇이 없고, 내구도가 1 이상 남아있어야 함) 이동. 없다면 가만히
		// 3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 로봇을 올린다.
		// 4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료. cnt 변수?

		// int[][] belt = new int[2][N];

		// 어차피 반으로 나눠서 생각하는 건데 그냥 한 줄이라고 생각하면?
		belt = new int[2 * N];
		robot = new boolean[N]; // 어차피 윗줄에만 있으니 N개만 생각하면 된다

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < 2*N; i++) {
			belt[i] = Integer.parseInt(st.nextToken());
		}
		int result = 0;
		int cnt = 0; // 내구도가 0이 된 칸을 세어 줄 변수
		int temp = 0;
		boolean temp2 = false;// 회전할 때 쓸 임시변수
		
		while (cnt < K) { 
			// 1. 벨트 회전
			temp = belt[2 * N - 1];
			temp2 = robot[N - 1];

			off();
			for (int i = 2 * N - 1; i > 0; i--) {
				// 한칸씩 이동하는데 맨 끝에 있는 것만 0으로
				belt[i] = belt[i - 1];
			}
			for (int i = N-1; i > 0; i--) {
				robot[i] = robot[i - 1];
			}
			belt[0] = temp;
			robot[0] = temp2;

			off();
			// 2. 로봇 이동
			// 가장 먼저 올라간 로봇부터니까 역으로
			for (int i = N-2; i >= 0; i--) { // N-2까지만 체크할 수 있는 이유는 로봇 내리기를 시도했으니 무조건 false 일 것
				if (robot[i]) {
					if (!robot[i + 1] && belt[i + 1] >= 1) { // 다음칸에 로봇이 없고 내구도가 1 이상이면
						robot[i + 1] = true; // 이동
						robot[i] = false;
						belt[i + 1]--; // 내구도 감소
						if (belt[i + 1] == 0)
							cnt++;
					}
				}
			}
			off();
			
			// 3. 로봇 올리기
			if (belt[0] != 0) {
				robot[0] = true;
				belt[0]--;
				if (belt[0] == 0)
					cnt++;
			}

			result++;
		}
		System.out.println(result);
	}// end of main

	public static void off() { // 로봇 내리기 (회전하거나 이동할 때마다 체크해 줘야 됨)
		if (robot[N - 1])
			robot[N - 1] = false;
	}

}// end of class