[BOJ] 컨베이어 벨트 위의 로봇 - 20055 (G5)

시간 제한	메모리 제한
1 초	256 MB

문제

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 내구도가 있다.

벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있던 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다.

풀이

시뮬레이션 문제이다. 주어진 규칙대로 정확하게 구현하면 된다.

코드

from collections import deque
N, K = map(int, input().split())
durability = deque(map(int, input().split()))
belt = deque([False] * (N * 2)) # belt 위에 로봇이 있는지 여부

PUT_IDX = 0
OUT_IDX = N - 1
round_num = 1

while True:
    # 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
    durability.rotate()
    belt.rotate()

    # 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다.
    belt[OUT_IDX] = False


    # 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
    for i in range(N - 2, -1, -1):
        # 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
        if not belt[i]:
            continue
        n_i = i + 1
        if not belt[n_i] and durability[n_i] >= 1:
            durability[n_i] -= 1
            belt[i] = False
            belt[n_i] = True
    
    # 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다.
    belt[OUT_IDX] = False

    # 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
    if durability[PUT_IDX]:
        durability[PUT_IDX] -= 1
        belt[PUT_IDX] = True
        
    # 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
    if durability.count(0) >= K:
        break
    round_num += 1

print(round_num)

시간 복잡도

O(N × 단계수)