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

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

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

설명

컨베이어 벨트는 2N만큼 회전하지만, 로봇은 N자리에서 OUT 되기 때문에 N만큼만 회전한다.

출처: https://jainn.tistory.com/81

출처: https://ryu-e.tistory.com/116

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

* 로봇은 올리는 위치에만 올리기 가능. 

* 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다.

* 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다.

* 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 

결과 출력: 몇 번째 단계가 진행중일 때 종료되었는지 출력

핵심 아이디어

• 회전 쉽게 하기 위해 deque 활용. Queue 구현을 위한 라이브러리. 큐는 FIFI 
• n개의 벨트만 로봇이 존재할 수 있다. 즉, 1에 올려서 n에 내린다. 따라서 n길이의 로봇 유무를 저장하는 배열 만든다. 
• 이동(회전) 후 내리는 위치에 도달했을 경우 내리는 거 잊지 않기.

코드 구현

# 회전을 쉽게 하기 위해 deque 사용
from collections import deque

n, k = map(int, input().split())
# 길이가 2인 벨트 deque로 구현
belt = deque(list(map(int, input().split())))
# n길이의 로봇 유무를 저장하는 배열 만들기
robot = deque([0] * n)

result = 0
# 몇 번 반복하는지 정해 지지 않아서 while loop 사용
while True:
	# 1단계씩 증가
	result += 1
	# 1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전
	belt.rotate(1)
	# 로봇과 함께 회전
	robot.rotate(1)
	# 로봇이 내리는 위치에 도달할 경우 즉시 내림
	robot[-1] = 0
	# 2. 이동가능하면 이동, 못하면 가만히
	# 이동 하려면 앞칸에 로봇 없고, 내구도 1이상
	# 내리는 칸이 n-1이므로 n-2부터 시작
	for i in range(n-2, -1, -1):
		if belt[i+1] >= 1 and robot[i+1] == 0 and robot[i] == 1:
			robot[i+1] = 1
			robot[i] = 0
			# 그 칸의 내구도 감소
			belt[i+1] -= 1
	# 내리는 위치에 도달한 경우, 즉시 내림
	robot[-1] = 0
	# 3. 올리는 위치에 내구도 0 아니면 로봇 올려
	if belt[0] != 0 and robot[0] != 1:
		robot[0] = 1 # 로봇 올리기
		belt[0] -= 1
	# 4. 내구도 0인 칸의 수가 k 이상이면 종료
	if belt.count(0) >= k:
		break
print(result)