백준_20055_컨베이어 벨트 위의 로봇

컨베이어 벨트 위의 로봇

문제

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다.

벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번 칸의 내구도는 $A_i$이다. 위의 그림에서 1번 칸이 있는 위치를 "올리는 위치", N번 칸이 있는 위치를 "내리는 위치"라고 한다.

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

컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 한다. 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.

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

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

입력

첫째 줄에 N, K가 주어진다. 둘째 줄에는 $A_1$, $A_2$, ..., $A_{2N}$이 주어진다.
2 ≤ N ≤ 100
1 ≤ K ≤ 2N
1 ≤ $A_i$ ≤ 1,000

출력

몇 번째 단계가 진행 중일때 종료되었는지 출력한다.

예제 입력 1

3 2
1 2 1 2 1 2

예제 출력 1

2

풀이 및 해설

출력값: 종료되었을 때 몇 번쨰 단계가 진행 중이었는지 출력
[조건]

• 박스 모양 로봇을 올리는 위치는 1번 칸, 내리는 위치는 N번 칸
• 로봇 올리는 위치에 올리거나(1번 칸), 로봇 이동할 때 내구도 1씩 감소
• 한 칸씩 이동할 때, 이동하려는 칸에 로봇 없고 그 칸의 내구도가 1 이상인 경우만 이동 가능
• 내구도가 0인 칸의 개수가 K개 이상이면 과정 종료, 그렇지 않으면 1번으로 이동

[문제 이해하기]

• 위의 1~4 과정 모두 처리한 경우가 하나의 단계임
• 컨베이어 벨트도 회전하고, 박스 모양 로봇도 한 칸씩 이동 가능
• 예제 입력 1) N=3, K=2 인 경우
  1. 초기 컨베이어 상태
  
  2. 1단계 처리
  2-1) 1 과정. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
  
  2-2) 2 과정. 벨트 위에 있는 로봇이 이동할 때 이동하려는 칸에 로봇이 없고, 그 칸의 내구도가 1 이상인 경우 이동 가능 → 이동시킬 로봇이 없음
  2-3) 3 과정. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
  
  2-4) 4 과정. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다. → 내구도가 0인 칸이 존재하지 않으므로 다음 단계로 넘어감
  3. 2단계 처리
  3-1) 1 과정. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
  
  3-2) 2 과정. 벨트 위에 있는 로봇이 이동할 때 이동하려는 칸에 로봇이 없고, 그 칸의 내구도가 1 이상인 경우 이동 가능
  
  3-3) 3 과정. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
  
  3-4) 4 과정. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다. → 내구도가 0인 칸이 2개 이므로 과정 종료
  

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [N, K] = input[0].split(' ').map(Number); // N: 컨베이어 벨트 길이, K: 내구도 0인 칸의 개수
const conveyor = input[1].split(' ').map(Number); // 컨베이어 벨트 각 칸의 내구도
const robots = Array.from({ length: N }, () => 0); // 로봇 위치

let stage = 0;
while (true) {
  stage++; // 다음 단계 진행
  // 1과정) 벨트 위에 있는 로봇과 함께 컨베이어 벨트 한 칸 회전
  const lastConveyor = conveyor.pop();
  conveyor.unshift(lastConveyor);
  robots.pop();
  robots.unshift(0);
  if (robots[N - 1] === 1) robots[N - 1] = 0;

  // 2과정) 벨트 위에 있는 로봇 회전하는 방향으로 한 칸 이동
  // (이때, 이동하려는 칸에 로봇이 있거나, 그 칸의 내구도가 1 이상인 경우만 이동 가능)
  // 내리는 위치에 오는 로봇은 즉시 내리기
  for (let i = N - 2; i >= 0; i--) {
    if (robots[i] && !robots[i + 1] && conveyor[i + 1] >= 1) {
      conveyor[i + 1]--;
      robots[i] = 0;
      robots[i + 1] = 1;
    }
  }
  if (robots[N - 1] === 1) robots[N - 1] = 0;

  // 3과정) 올리는 위치에 있는 칸의 내구도가 0이 아닌 경우 로봇 올리기
  if (conveyor[0] !== 0) {
    robots[0] = 1;
    conveyor[0]--;
  }
  // 4과정) 내구도가 0인 칸의 개수가 K개 이상인 경우 과정 종료, 아니면 다음 단계 진행
  const count = conveyor.filter((c) => c === 0).length;
  if (count >= K) break;
}
console.log(stage);

unshift 메서드($O(N)$) 사용하지 않고 인덱스 이용하기

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [N, K] = input[0].split(' ').map(Number); // N: 컨베이어 벨트 길이, K: 내구도 0인 칸의 개수
const conveyor = input[1].split(' ').map(Number); // 컨베이어 벨트 각 칸의 내구도
const robots = Array.from({ length: 2 * N }, () => false); // 로봇 위치

let stage = 0;
let zeroCount = 0; // 내구도가 0인 컨베이어 개수
let [start, end] = [0, N - 1];

// 4과정) 내구도가 0인 칸의 개수가 K개 이상인 경우 과정 종료, 아니면 다음 단계 진행
while (zeroCount < K) {
  stage++; // 다음 단계 진행

  // 1과정) 벨트 위에 있는 로봇과 함께 컨베이어 벨트 한 칸 회전 (원형)
  start = (start - 1 + 2 * N) % (2 * N);
  end = (end - 1 + 2 * N) % (2 * N);
  robots[end] = false; // 내리는 위치에 로봇 있으면 내림

  // 2과정) 벨트 위에 있는 로봇 회전하는 방향으로 한 칸 이동
  // (이때, 이동하려는 칸에 로봇이 있거나, 그 칸의 내구도가 1 이상인 경우만 이동 가능)
  // 내리는 위치에 오는 로봇은 즉시 내리기
  for (let i = 1; i < N; i++) {
    // 가장 먼저 올라간 로봇부터 순서대로 처리해야 하므로 뒤에서 앞으로 순회
    const current = (end - i + 2 * N) % (2 * N);
    const next = (current + 1) % (2 * N);
    if (robots[current] && !robots[next] && conveyor[next] >= 1) {
      robots[current] = false;
      robots[next] = true;
      conveyor[next]--;
      if (conveyor[next] === 0) zeroCount++;
    }
  }
  robots[end] = false; // 내리는 위치에 로봇 있으면 내림

  // 3과정) 올리는 위치에 있는 칸의 내구도가 0이 아닌 경우 로봇 올리기
  if (!robots[start] && conveyor[start] >= 1) {
    robots[start] = true;
    conveyor[start]--;
    if (conveyor[start] === 0) zeroCount++;
  }
}
console.log(stage);