[백준 20055] 컨베이어 벨트 위의 로봇 (C++)

A. 문제설명

 

www.acmicpc.net/problem/20055

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

문제에 대한 자세한 설명은 링크 참조

 

1. 다음과 같은 형태의 컨베이어 벨트가 존재

2. 벨트는 1~2N의 위치로 시계방향으로 회전하며, 1번 위치에서 로봇이 탑승, N번 위치에서 로봇이 하차함

3. 컨베이어 벨트를 이용해 로봇을 한쪽에서 반대편으로 옮기려고 하는데, 다음의 규칙에 따라 이동함

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

4. 종료되었을 때 수행된 단계의 갯수를 구하라

 

B. 접근법

시뮬레이션

 

원형 큐 형태의 컨베이어 벨트를 시뮬레이션하는 문제이다. 문제 조건에서 고려해야할 점이 1. 내구도 / 2. 로봇의 탑승 위치 / 3. 컨베이어 벨트의 회전 이 세가지인데, 이를 고려하여 구현해주도록 한다.

내구도와 로봇의 위치를 conveyorDurable / conveyorRobots 배열에 각각 기록하여 매 턴마다 해당 배열의 엔트리를 회전시켜가는 방식으로 구현하였다.

 

여기서 조심해야할 점은 벨트를 회전하기 전/후에 N번 위치에 있는 로봇을 하차시켜야한다는 점이다. (여기서 하차 못하고 N번 로봇이 N+1 위치로 가는 경우 문제의도와 다르게 동작하여 오답이 발생함)

 

C. 풀이

1. 회전 전, 내려가는 위치 로봇 있으면 먼저 내려감

2. 벨트가 한 칸 회전

3. 회전 후, 내려가는 위치 로봇 있으면 먼저 내려감

4. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동

5. 올라가는 위치에 로봇이 없다면 로봇을 하나 올림

6. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료. 그렇지 않다면 1번으로 돌아가 반복

 

D. 내 코드