🏆 알고리즘 문제 풀이

📌 문제 정보

• 문제명 : 컨베이어 벨트 위의 로봇
• 문제 번호 : 20055
• 출처 : https://www.acmicpc.net/problem/20055
• 난이도 : G5
• 유형 : 시뮬레이션 / 구현

---

🧐 문제 설명

길이 2N의 컨베이어 벨트 위에 로봇이 이동하며,
벨트의 내구도(durability) 가 0이 되는 칸이 K개 이상일 때까지 과정을 시뮬레이션하는 문제이다.

• 벨트는 회전하며 연결되어 있다.
• 로봇은 올라가는 위치에서만 올라갈 수 있으며,
  내리는 위치에 도달하면 반드시 내려야 한다.
• 로봇은 앞에 로봇이 없고, 이동할 칸의 내구도가 1 이상일 경우에만 전진할 수 있다.
• 한 단계가 끝날 때마다 내구도가 0인 칸의 개수를 세며,
  K 이상이면 종료한다.

👉 출력 : 종료될 때까지의 단계 수

---

💡 접근 방법

1. 벨트와 로봇의 상태를 함께 회전

   • 내구도 배열(belt[])과 로봇 배열(robot[])을 한 칸씩 오른쪽으로 회전시킴.
   • 내리는 위치(N-1)에는 로봇이 있더라도 무조건 내려야 함.

2. 로봇 이동

   • 오른쪽부터 순차적으로 이동 가능 여부를 검사.
   • 다음 칸이 비어 있고 내구도가 1 이상이면 전진 후 내구도 감소.

3. 로봇 올리기

   • 올라가는 위치(0번 칸)에서 내구도가 남아 있다면 로봇을 올림.

4. 내구도 0인 칸 세기

   • 매 단계마다 내구도가 0인 칸의 개수를 계산하고 K 이상이면 종료.

---

📝 문제 설계

✅ 변수 정의

변수	설명
N	벨트의 절반 길이
K	내구도 0인 칸의 임계값
belt[]	벨트 각 칸의 내구도
robot[]	로봇 존재 여부 (true면 로봇 존재)
step	현재 단계 수
zeroCnt	내구도 0인 칸 개수

---

✅ 알고리즘 흐름

1. belt 배열(길이 2N)과 robot 배열(길이 N) 초기화
2. 각 단계마다 다음 순서 수행
   1️⃣ 벨트 및 로봇 회전
   2️⃣ 로봇 이동
   3️⃣ 로봇 올리기
   4️⃣ 내구도 0 칸 개수 검사
3. 내구도 0 칸 ≥ K이면 종료
4. 총 단계 수(step) 출력

---

✅ 시간 복잡도

• 각 단계에서 최대 O(N) 연산
• 내구도 0 칸이 K(≤ 2N)개 될 때까지 진행
  → O(N × 단계 수)
  N ≤ 100이므로 충분히 빠름

---

💡 사용 알고리즘

• 시뮬레이션 (Simulation)

---

📚 시뮬레이션을 선택한 근거

1. 각 단계의 동작이 명확하게 정의되어 있고, 순차적으로 실행해야 하는 문제이다.
2. 수학적 최적화나 탐색보다, 상태 변화를 그대로 구현하는 것이 직관적이고 빠르다.
3. 각 과정이 독립적이므로 절차형으로 구현하기에 적합하다.

---

입력 & 출력 예시

---

🧑‍💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();  // 벨트 위 칸 수 (한쪽)
        int K = sc.nextInt();  // 내구도가 0인 칸이 K개 이상이면 종료

        int size = 2 * N;      // 벨트 전체 길이
        int[] belt = new int[size];
        for (int i = 0; i < size; i++) {
            belt[i] = sc.nextInt();
        }

        boolean[] robot = new boolean[N];  // 로봇 위치 관리 (0~N-1까지만)
        int zeroCnt = 0;
        int step = 0;

        while (true) {
            step++;

            // 1️⃣ 벨트 회전
            int last = belt[size - 1];
            for (int i = size - 1; i > 0; i--) {
                belt[i] = belt[i - 1];
            }
            belt[0] = last;

            // 로봇 회전
            for (int i = N - 1; i > 0; i--) {
                robot[i] = robot[i - 1];
            }
            robot[0] = false;   // 올라가는 위치에는 회전 시 로봇 없음
            robot[N - 1] = false; // 내리는 위치 로봇 내림

            // 2️⃣ 로봇 이동
            for (int i = N - 2; i >= 0; i--) {
                if (robot[i] && !robot[i + 1] && belt[i + 1] > 0) {
                    robot[i] = false;
                    robot[i + 1] = true;
                    belt[i + 1]--;
                }
            }
            robot[N - 1] = false; // 내리는 위치 로봇 내림

            // 3️⃣ 올라가는 위치에 로봇 올리기
            if (belt[0] > 0 && !robot[0]) {
                robot[0] = true;
                belt[0]--;
            }

            // 4️⃣ 내구도 0 칸 개수 세기
            zeroCnt = 0;
            for (int durability : belt) {
                if (durability == 0) zeroCnt++;
            }

            // 5️⃣ 종료 조건
            if (zeroCnt >= K) break;
        }

        System.out.println(step);
        sc.close();
    }
}

---

🔍 코드 해설

1️⃣ 벨트 회전

int last = belt[size - 1];
for (int i = size - 1; i > 0; i--) {
    belt[i] = belt[i - 1];
}
belt[0] = last;

• 벨트가 한 칸 오른쪽으로 회전
• 마지막 칸의 내구도가 첫 번째로 이동

---

2️⃣ 로봇 회전

for (int i = N - 1; i > 0; i--) {
    robot[i] = robot[i - 1];
}
robot[0] = false;
robot[N - 1] = false;

• 로봇도 벨트와 함께 이동
• 내리는 위치에 있는 로봇은 반드시 내려감

---

3️⃣ 로봇 이동

for (int i = N - 2; i >= 0; i--) {
    if (robot[i] && !robot[i + 1] && belt[i + 1] > 0) {
        robot[i] = false;
        robot[i + 1] = true;
        belt[i + 1]--;
    }
}

• 오른쪽(내리는 방향)부터 검사
• 다음 칸이 비어 있고 내구도가 남아 있으면 이동
• 이동 시 내구도 감소

---

4️⃣ 로봇 올리기

if (belt[0] > 0 && !robot[0]) {
    robot[0] = true;
    belt[0]--;
}

• 올라가는 위치(0번 칸)에서 내구도가 1 이상이면 로봇을 올림

---

5️⃣ 종료 조건

if (zeroCnt >= K) break;

• 내구도가 0인 칸의 개수가 K 이상이면 종료