[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)

 

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