728x90

[BOJ 20055] 컨베이어 벨트 위의 로봇 — 외우지 말고 “규칙을 번역”해서 푸는 시뮬레이션

이 문제는 아이디어가 어려워서가 아니라, 규칙을 한 단계씩 정확히 재현하지 못해서 틀리는 문제다.
결국 해야 할 일은 하나다.

상태(belt/robots)를 잡고, 매 단계 규칙을 그대로 실행한다.

1) 왜 “시뮬레이션”이라고 바로 결정하는가

문제는 매 step마다 아래 순서를 강제한다.

벨트 회전
로봇 이동
로봇 올림
내구도 0 개수로 종료

최적화를 고민할 게 아니라, 상태 변화가 정확하면 정답이다.

2) “왜 belt는 2N이 필요하지?” (회전 때문에)

로봇은 위쪽(0~N-1)에서만 의미가 있지만, 벨트는 2N 전체가 원형 회전한다.

회전 후 0번 칸은 원래 2N-1번 칸이 올라온다.

// 회전 전: [a0 a1 a2 | a3 a4 a5]
// 회전 후: [a5 a0 a1 | a2 a3 a4]

그래서 belt는 무조건 2N이 필요하다.

3) 상태(state) 잡기: belt + robots

필요한 상태는 딱 두 개다.

belt[2N]: 내구도
robots[2N]: 로봇 유무(편하게 belt와 같이 회전시키려고 2N으로 둠)

const belt = input[1].split(" ").map(Number); // length = 2N
const robots = Array(belt.length).fill(false); // length = 2N

이 방식의 장점:

belt와 robots를 같이 rotate하면 “로봇이 벨트에 붙어서 이동”이 자연스럽게 구현된다.

4) 인덱스 약속 (0-index)

복잡해지지 않게 딱 2개만 고정한다.

올리는 칸: 0
내리는 칸: N-1

const UP = 0;
const DOWN = n - 1;

5) 한 step 템플릿 (이 문제의 핵심)

정답은 그냥 이 순서를 루프에 박는 것이다.

회전 → (즉시 하차) → 이동 → (즉시 하차) → 올림 → 종료 체크

여기서 제일 큰 함정:

✅ 하차는 2번 한다

회전으로 DOWN에 도착할 수 있음 → 즉시 하차
이동으로 DOWN에 들어갈 수 있음 → 즉시 하차

그래서 아래 두 줄은 “습관”이어야 한다.

robots[n - 1] = false; // 회전 직후 하차
...
robots[n - 1] = false; // 이동 직후 하차

6) (1) 회전 구현: belt와 robots를 함께 회전

회전은 “맨 뒤를 맨 앞으로”다.

function rotate(belt, robots) {
  belt.unshift(belt.pop());
  robots.unshift(robots.pop());
}

step에서 이렇게 쓴다:

function rotate(belt, robots) {
  belt.unshift(belt.pop());
  robots.unshift(robots.pop());
}

7) (2) 로봇 이동: 왜 뒤에서 앞으로인가

로봇 이동은 내리는 칸에 가까운 로봇부터 처리해야 한다.
그래서 i = n-2 → 0 역순이 안전하다.

이동 조건은 3개다.

현재 칸에 로봇이 있다
다음 칸에 로봇이 없다
다음 칸 내구도 > 0

그리고 이동하면 도착 칸 내구도 감소.

for (let i = n - 2; i >= 0; i--) {
  if (robots[i] && !robots[i + 1] && belt[i + 1] > 0) {
    robots[i] = false;
    robots[i + 1] = true;
    belt[i + 1]--;          // 도착 칸 내구도 감소
  }
}
robots[n - 1] = false;      // 이동 후 즉시 하차 (2번째)

8) (3) 로봇 올림

올리는 칸(0)에 로봇이 없고 내구도가 남아있으면 올린다.

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

9) (4) 종료 조건: 내구도 0의 개수 ≥ K

일단 안전하게 전체를 세는 방식(복습/실전에 충분히 안정적).

function countZero(belt) {
  let cnt = 0;
  for (let i = 0; i < belt.length; i++) {
    if (belt[i] === 0) cnt++;
  }
  return cnt;
}

step 끝에서

if (countZero(belt) >= k) break;

✅ 최종 코드 (JavaScript / Node.js)

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
rl.on("line", (line) => input.push(line));
rl.on("close", () => {
  const [n, k] = input[0].split(" ").map(Number);
  const belt = input[1].split(" ").map(Number); // length = 2n
  console.log(solution(n, k, belt));
  process.exit(0);
});

function rotate(belt, robots) {
  belt.unshift(belt.pop());
  robots.unshift(robots.pop());
}

function countZero(belt) {
  let cnt = 0;
  for (let i = 0; i < belt.length; i++) {
    if (belt[i] === 0) cnt++;
  }
  return cnt;
}

function solution(n, k, belt) {
  let step = 0;
  const robots = Array(belt.length).fill(false);

  while (true) {
    step++;

    // 1) 벨트 회전
    rotate(belt, robots);
    // 회전 직후 내리는 칸 즉시 하차
    robots[n - 1] = false;

    // 2) 로봇 이동 (뒤 -> 앞)
    for (let i = n - 2; i >= 0; i--) {
      if (robots[i] && !robots[i + 1] && belt[i + 1] > 0) {
        robots[i] = false;
        robots[i + 1] = true;
        belt[i + 1]--;
      }
    }
    // 이동 후 내리는 칸 즉시 하차 (하차 2번)
    robots[n - 1] = false;

    // 3) 로봇 올림
    if (!robots[0] && belt[0] > 0) {
      robots[0] = true;
      belt[0]--;
    }

    // 4) 종료 체크
    if (countZero(belt) >= k) break;
  }

  return step;
}