[Python] 20055. 컨베이어 벨트 위의 로봇

www.acmicpc.net/problem/20055

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

---

 

Point

• 내구도 0칸에는 로봇이 올라가지 못하며, 내려가기만 가능
• 벨트 회전 시 로봇 좌표 변경
• 이동하려는 칸에 로봇이 없어야하며 내구도 1이상
• 올라가는 위치에서 로봇이 없어야만 올림

Tip

• deque를 사용해 구현하면 코드가 간결해짐
• 로봇 좌표를 체크할 check 배열을 생성해서 계속 업데이트 해줌

 

메모리 (제한: MB)

129232 KB

시간 (제한: 초)

688 ms

결과

100%

from collections import deque
import sys

def cnt_zeros():
    global k
    cnt = 0
    for a in A:
        if a == 0:
            cnt += 1
            if cnt == k:
                return True
    return False

input = sys.stdin.readline

n,k = map(int, input().split())
A = deque(list(map(int, input().split())))
check = [False]*n
step = 1
robots = deque()

while True:
    # 회전
    a = A.pop()
    A.appendleft(a)

    # 회전으로 로봇 위치 변경
    if robots:
        tmp = deque()
        while robots:
            r = robots.popleft()
            check[r] = False
            r += 1
            if r == n-1:
                pass
            else:
                check[r] = True
                tmp.append(r)
        robots = tmp

        # 로봇이 있다면 순차적으로 이동
        tmp = deque()
        while robots:
            r = robots.popleft()
            # 다른 로봇이 있거나 내구도가 0 일 경우
            if check[r+1] or A[r+1] == 0:
                tmp.append(r)
            elif not check[r+1] and A[r+1] != 0:
                check[r] = False
                r += 1
                A[r] -= 1
                if r == n-1:
                    pass
                else:
                    check[r] = True
                    tmp.append(r)
        robots = tmp

    # 로봇 올림
    if not check[0] and A[0] > 0:
        robots.append(0)
        A[0] -= 1
        check[0] = True

    # 내구도 검사
    if cnt_zeros():
        break

    step += 1

print(step)

 

문제를 푸는데 도움이 된 테스트 케이스