컨베이어 벨트 위의 로봇

문제 설명

  길이가 N인 컨베이어 벨트가 있고 길이가 2N인 벨트가 있다. 벨트가 한 칸씩 이동하는데, 2n 번째 벨트는 1로 이동하는 돌아가는 형태이다. 로봇은 컨베이어 벨트에만 존재할 수 있는데, 만일 로봇이 어느 순서든 n칸에 위치한다면 해당 로봇을 내려준다. 또한 로봇은 1번 칸에서만 올릴 수 있다. 참고로 벨트의 내구도는 로봇이 이동하거나 로봇을 올렸을 때마다 1씩 감소한다. 내구도가 0인 칸의 개수가 k개 이상이면 종료하는데, 몇 단계에서 종료되는지를 구하는 문제다.

 

1. 벨트가 움직이면 로봇도 함께 한 칸씩 움직인다.

2. 제일 먼저 컨베이어 벨트에 올라간 로봇부터, 벨트의 회전 방향 대로 한 칸 씩 움직일 수 있다. 만일 이동할 수 없으면 이동하지 않는다.

  2-1. 이동할 수 없는 경우의 수는 로봇이 이동하고자 하는 칸에 로봇이 있거나 해당 칸의 내구도가 0이하인 경우이다.

3. 올리는 위치(1)에 로봇을 올린다.

4. 내구도가 0인 칸의 수가 k개 이상이면 과정을 종료한다. 그렇지 않다면 1번부터 다시 시작한다.

 

솔직히 난 정답을 맞추긴 했지만, 문제를 약간 잘못 이해하고 풀었다. 로봇은 벨트 위에서만 움직이는데 나는 로봇을 컨베이어 벨트로까지 이동시켜서 풀었기 때문이다. 근데, 그렇게 해도 틀리지 않는 걸 보니...

 

https://www.acmicpc.net/problem/20055

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

 

새로 이해한 문제

그러니까 일단 컨베이어 벨트가 0부터 2N까지 있다고 생각한다. 그리고 컨베이어 벨트 위의 1부터 N까지가 벨트이다. 그리고 이 벨트에 로봇이 올라가는 것이다. 근데, 컨베이어 벨트가 한 칸씩 움직이니까 벨트도 같이 움직이게 되는 것이다.

 

문제 풀이

첫 번째 풀이

초반에는 큐인가? 스택인가? 했지만, 그냥 리스트로 컨베이어 벨트의 내구도를 받아서 돌려줬다.

1. 일단 내구도가 0인 칸의 갯수가 k개 이상이면 탈출하도록 했다. 해당 부분은 4번째이지만, 난 while문을 돌릴 때 제일 위에 탈출문이 있는 것을 좋아하기 때문에 제일 먼저 작성해줬다.

 

2. 그 다음 벨트를 회전한다. 다른 사람들의 풀이를 보니 python의 rotate 함수를 써서 배열을 회전해줬다. 나는 직접 회전하는 것을 구해줬고. 벨트를 회전하는 방식은 tmp에다가 A 값을 깊은 복사로 넣어준 다음에 tmp[i]의 값을 A[i+1]에 넣어주는 방식이다. 즉, 한 칸 씩 뒤로 밀어준다고 생각하면 된다. 그리고 tmp의 맨 마지막 값을 A의 맨 처음 값에다가 넣어주면 된다.

 

벨트를 회전했으니 이제 컨베이어 벨트에 있는 로봇들을 회전해야 하는 차례이다. 여기서 내가 잘못 이해한 부분이 드러나는데, 로봇은 컨베이어 벨트에만 있기에 1부터 n까지 존재하지만 나는 로봇이 벨트에도 있다고 생각해서 1부터 2n까지로 범위를 잡았다. 근데 안 틀렸다.  아무튼 나는 robots라는 배열에다가 로봇의 위치를 넣어줬다. 제일 먼저 들어온 로봇부터 움직여야 하니까 robots[0]=1이란 의미는 0번째에 들어온 로봇이 현재 컨베이어 벨트 1에 위치해있다는 의미이다.

 

그렇기에 robots에서 값을 가지고 와서 하나씩 증가해준다. 만일 n-1이 되어 내리는 칸이 되면 delRobot에 해당 로봇 값을 넣어준다. 왜냐하면 반복문을 돌릴 때 삭제를 해주면 인덱스가 하나 사라져서 에러가 나기 때문이다. 그리고 2n-1에 도달한 로봇이 있다면 해당 로봇의 위치를 0으로 돌려준다.

 

그리고 delRobot가 0이 아니라서 삭제할 값이 있으면 robots에 해당 값을 삭제해주고  delRobot의 값을 0으로 돌려준다.

 

이렇게 풀지 않고 다른 사람처럼 robots[] 배열을 n만큼 만들어준 다음에 해당 인덱스에 로봇이 존재하면 1, 존재하지 않으면 0으로 표시해주는 방법이다.

 

3. 그리고 로봇을 한 칸씩 움직인다. 이 방법도 위에서 로봇을 회전하는 방식대로 하면 되는데, 만일 새로 이동하는 칸에 로봇이 있거나 내구도가 0이하이면 로봇을 이동시키지 않는다. 또한 로봇을 이동했는데, 내리는 위치라면 해당 로봇을 delRobot에 넣어서 삭제 로봇값을 표시한다.

 

그리고  delRobot에 값이 있다면 2에서 했던 것처럼 robots에서 값을 하나 삭제해준다.

 

4. 마지막으로 올리는 위치 0에 내구도가 0이상이면 로봇을 올려준다.

 

코드

import sys
import copy

n, k = map(int, sys.stdin.readline().rstrip().split(" "))
A = list(map(int, sys.stdin.readline().rstrip().split(" ")))
robots = [] #로봇의 위치를 알려줌
zero = 0
answer = 0

while True:
    zero = 0
    # 4. 내구도가 0인 칸의 개수가 k개 이상이면 종료한다.
    if A.count(0) >= k:
        break

    # 1. 벨트를 회전한다.
    # 제일 오른쪽(마지막 값)에서 하나 빼서 제일 왼쪽에 붙여줌
    tmp = copy.deepcopy(A)
    for i in range(0, len(tmp)-1):
        A[i+1] = tmp[i]
    A[0] = tmp[-1]

    # 벨트와 로봇이 함께 움직이니 로봇의 위치 조정이 필요
    delRobot = 0
    for j in range(len(robots)):
        tmpMove = robots[j]+1
        robots[j] = tmpMove
        if tmpMove == (n-1): # 회전했더니 n번째 칸에 도달한 로봇이 있다. -> 해당 로봇 삭제
            delRobot = robots[j]
        if robots[j] == len(A)-1: # 2n에 도달한 로봇이 있으면 1로 맞춰준다.
            robots[j] = 0

    if delRobot != 0:
        robots.remove(delRobot)
        delRobot = 0

    # 2. 가장 먼저 올라간 로봇부터 벨트가 회전하는 방향으로 움직인다.
    for index, robot in enumerate(robots):
        tmpMove = robot + 1
        # 만일 새로 이동하려는 위치가 2n이라면 1로 맞춰준다.
        if tmpMove == len(A)-1:
            tmpMove = 0
        # 만일 새로 이동하려는 칸에 로봇이 있거나 해당 칸의 내구도가 0이라면 이동하지 않는다.
        if tmpMove in robots:
            continue
        elif A[tmpMove] > 0:
            robots[index] = tmpMove
            A[robots[index]] -= 1
            if robots[index] == (n-1):
                delRobot = robots[index]

    if delRobot != 0:
        robots.remove(delRobot)
        delRobot = 0

    # 3. 올리는 위치의 칸의 내구도가 0이 아니면 로봇을 올린다.
    if A[0] > 0:
        A[0] -= 1
        robots.append(0)

    answer += 1

print(answer)