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

문제

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

 

문제 풀이

 시뮬레이션 문제 중에서 쉬운 편에 속하며, 문제에 요구하는 사항대로 구현하면 되는 문제이다. 컨베이어 벨트가 회전하는 것은 `deque.rotate()`를 활용하면 쉽게 구현할 수 있다.

 

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

 문제에서 제시된 위의 과정을 순서대로 구현하면 된다. 문제를 풀면서 어려운 사항은 없었지만 `bool` 타입을 사용하면 속도가 느린지 57% 통곡의 벽이 있었다. (57%에서 계속 시간 초과가 발생했다.)

 

코드

from sys import stdin
from collections import deque


if __name__ == '__main__':
    N, K = map(int, stdin.readline().split())
    A = deque(map(int, stdin.readline().split()))
    robot = deque([0] * N)

    stage = 0

    # 4. 컨베이어 벨트의 내구도가 0인 것이 K개 이상인 경우까지 반복
    while A.count(0) < K:
        # 1. 벨트와 로봇을 한 칸 회전
        # (clockwise)
        A.rotate(1)
        robot.rotate(1)

        # 내려갈 위치에 로봇을 내림
        robot[-1] = 0

        # 2. 조건을 만족하는 경우 로봇을 움직임
        for idx in range(N - 2, -1, -1):
            # 로봇이 없으면 패스
            if robot[idx] == 0:
                continue
            # 다음칸에 로봇이 없고 내구도가 있다면, 옮김
            if robot[idx + 1] == 0 and A[idx + 1]:
                A[idx + 1] -= 1
                robot[idx + 1] = 1
                robot[idx] = 0

        # 이동 후에도 내려갈 곳에 있다면 내림
        robot[-1] = 0

        # 3. 첫 번째 칸에 올릴 수 있다면 올리기.
        if A[0] and robot[0] == 0:
            A[0] -= 1
            robot[0] = 1

        stage += 1

    print(stage)