[BOJ/Java] 컨베이어 벨트 위의 로봇 (20055)

컨베이어 벨트 위의 로봇 (20055)

1. 문제 분석

문제 개요

• 주어진 컨베이어 벨트 위에 로봇을 올리고, 로봇을 이동시키는 작업을 반복하면서 각 칸에 있는 내구도가 0이 되는 칸의 개수가 K개 이상이 될 때까지 반복을 수행한다. 각 단계에서 로봇을 이동시키고, 로봇을 올리며 내구도를 갱신하는 작업을 정확히 구현해야 한다.

입력 형식

• 첫 번째 줄에는 두 정수 N, K가 주어진다. N은 컨베이어 벨트의 반 개수, K는 내구도가 0인 칸이 되어야 하는 목표값이다.
• 두 번째 줄에는 각 칸의 내구도가 주어진다. 각 칸의 내구도는 1 이상 100 이하의 자연수로 주어진다.

출력 형식

• 목표값 K에 도달할 때까지 진행된 단계를 출력한다. 즉, K개의 칸의 내구도가 0이 될 때까지의 횟수를 출력한다.

2. 알고리즘 종류

• 이 문제는 시뮬레이션 알고리즘을 사용하는 문제이다. 해당 문제는 로봇의 이동과 내구도 갱신, 로봇의 배치 등을 정확하게 구현해야 하므로, 각 단계를 순차적으로 처리하면서 상태를 업데이트해야 한다.

3. 주요 부분 및 코드 작성 방법

1. 회전 및 로봇의 이동

• rotate 함수는 컨베이어 벨트를 한 칸 회전시키며, 벨트의 내구도 및 로봇 위치를 갱신한다. 회전 후, 로봇이 벨트에서 내려지게 된다.
• move 함수는 로봇들을 한 칸씩 이동시키며, 이동한 칸의 내구도를 감소시킨다. 내구도가 0이 된 칸은 카운트된다.

2. 로봇 배치

• placeRobot 함수는 벨트의 첫 번째 칸에 로봇을 올릴 수 있는지 확인하고, 내구도를 감소시키면서 로봇을 배치한다.

3. 내구도 체크

• putdown 함수는 내구도가 0인 칸에서 로봇을 내린다. 이는 로봇이 더 이상 이동할 수 없게 되면 벨트에서 떨어지도록 처리된다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());

  • 첫 번째 줄에서 N과 K를 입력받는다. N은 컨베이어 벨트의 반 개수, K는 내구도가 0이 된 칸이 K개 이상이 될 때까지 진행되는 횟수이다.

• 초기화 및 입력된 위치 저장

    conveyorBelt = new LinkedList<>();
    robots = new LinkedList<>();
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N * 2; i++) {
        conveyorBelt.add(Integer.parseInt(st.nextToken()));
        robots.add(false);
    }

  • conveyorBelt와 robots를 초기화한다. conveyorBelt는 컨베이어 벨트의 내구도를 저장하고, robots는 각 칸에 로봇이 있는지 여부를 저장한다.

• 알고리즘 수행

    int result = 0;
    while (zeroCount < K) {
        result++;
        rotate();
        move();
        placeRobot();
    }
    System.out.println(result);

  • 목표인 K개 이상의 내구도가 0인 칸을 만들 때까지 시뮬레이션을 반복한다. 각 단계마다 회전, 이동, 로봇 배치를 수행한다.

(2) rotate 함수

• 회전 처리

    conveyorBelt.addFirst(conveyorBelt.remove(conveyorBelt.size() - 1));
    robots.addFirst(robots.remove(robots.size() - 1));

  • 컨베이어 벨트를 한 칸 회전시키고, 로봇의 위치도 회전시킨다.

• 내려놓기

    putdown();

  • 회전 후, 내구도가 0인 칸에서 로봇을 내린다.

(3) move 함수

• 로봇 이동 및 내구도 감소

    for (int i = N - 2; i >= 0; i--) {
        if (robots.get(i) && !robots.get(i + 1) && conveyorBelt.get(i + 1) > 0) {
            robots.set(i, false);
            robots.set(i + 1, true);
            conveyorBelt.set(i + 1, conveyorBelt.get(i + 1) - 1);
            if (conveyorBelt.get(i + 1) == 0) zeroCount++;
        }
    }

  • 로봇이 이동할 수 있는지 확인하고, 이동시키며 내구도를 감소시킨다. 내구도가 0이 되면 zeroCount를 증가시킨다.

• 내려놓기

    putdown();

  • 내구도가 0인 칸에서 로봇을 내린다.

(4) putdown 함수

• 로봇 내리기

    if (robots.get(N - 1)) robots.set(N - 1, false);

  • 마지막 칸에 있는 로봇을 내린다.

(5) placeRobot 함수

• 로봇 배치 및 내구도 감소

    if (conveyorBelt.get(0) > 0) {
        robots.set(0, true);
        conveyorBelt.set(0, conveyorBelt.get(0) - 1);
        if (conveyorBelt.get(0) == 0) zeroCount++;
    }

  • 첫 번째 칸에 내구도가 0이 아닌 경우 로봇을 배치하고, 내구도를 감소시킨다. 내구도가 0이 되면 zeroCount를 증가시킨다.

5. 전체 코드

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

public class BOJ20055 {
    public static int N, K, zeroCount = 0;
    public static LinkedList<Integer> conveyorBelt;
    public static LinkedList<Boolean> robots;

    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());

        conveyorBelt = new LinkedList<>();
        robots = new LinkedList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N * 2; i++) {
            conveyorBelt.add(Integer.parseInt(st.nextToken()));
            robots.add(false);
        }

        int result = 0;
        while (zeroCount < K) {
            result++;
            rotate();  // 회전
            move();    // 로봇 이동
            placeRobot();  // 로봇 배치
        }
        System.out.println(result);  // 결과 출력
    }

    public static void rotate() {
        conveyorBelt.addFirst(conveyorBelt.remove(conveyorBelt.size() - 1));  // 컨베이어 벨트 회전
        robots.addFirst(robots.remove(robots.size() - 1));  // 로봇 위치 회전

        putdown();  // 로봇 내리기
    }

    public static void move() {
        for (int i = N - 2; i >= 0; i--) {
            if (robots.get(i) && !robots.get(i + 1) && conveyorBelt.get(i + 1) > 0) {
                robots.set(i, false);  // 현재 칸에서 로봇 내리기
                robots.set(i + 1, true);  // 다음 칸에 로봇 올리기
                conveyorBelt.set(i + 1, conveyorBelt.get(i + 1) - 1);  // 내구도 감소

                if (conveyorBelt.get(i + 1) == 0) zeroCount++;  // 내구도가 0이면 카운트 증가
            }
        }

        putdown();

  // 로봇 내리기
    }

    public static void putdown() {
        if (robots.get(N - 1)) robots.set(N - 1, false);  // 마지막 칸의 로봇 내리기
    }

    public static void placeRobot() {
        if (conveyorBelt.get(0) > 0) {
            robots.set(0, true);  // 첫 번째 칸에 로봇 올리기
            conveyorBelt.set(0, conveyorBelt.get(0) - 1);  // 내구도 감소

            if (conveyorBelt.get(0) == 0) zeroCount++;  // 내구도가 0이면 카운트 증가
        }
    }
}