BOJ - 컨베이어 벨트 위의 로봇 20055번 (python)

❓ 문제 - 백준 컨베이어 벨트 위의 로봇 20055번 - python 풀이법

 

출처 

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

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

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 컨베이어 벨트의 내구성을 저장할 큐와 로봇의 정보를 저장할 큐를 사용하며, 다음 로직을 while 문으로 반복적으로 수행한다.
• 컨베이어 벨트와 로봇이 같이 한칸씩 옆으로 돌아가므로 queue의 rotate(1) 을 활용한다. 로봇은 n-1에서 퇴장하므로 회전 후 제거해준다.
•  로봇의 움직임은 가장 처음 놓아진 로봇 부터 시작한다는 조건에서 인덱스 끝부터 처리한다. 로봇 n-2 ~ 0번 인덱스 까지 한칸씩 움직일 수 있으면 움직이고, 로봇은 n-1에서 퇴장하므로 회전 후 제거해준다. 로봇이 움직인다면 컨베이어 벨트의 내구성을 -1 해준다.
• 만약 로봇을 내려놓을 수 있는 인덱스(0)의 컨베이어 벨트의 내구성이 1이상이면 로봇을 새로 추가해준다. 
• 만약 컨베이어 벨트의 내구성이 0인 구역이 k개 이상이라면 컨베이어벨트를 종료시키고 정답을 출력한다.

 

2. 문제 풀면서 느낀점

• 회전 문제는 큐의 rotate를 활용하자. 그리고 컨베이어 벨트와 로봇이 같이 회전하는 구간이 있으므로 로봇도 큐로 구현해야한다.
• 문제에서 주어진 가장 먼저 놓여진 로봇부터 움직임을 시작한다는 것은 로봇의 번호를 저장해서 처리하는 것보다 인덱스 끝 ~ 처음으로 이동을 처리하는 것이 훨씬 더 간편하게 구현할 수 있다.

 

💻 소스코드

from collections import deque

n, k = map(int, input().split())
q = deque()
lst = list(map(int, input().split()))
q.extend(lst)
answer = 0

robot = deque([0]*(n*2))

while True:
    q.rotate(1)
    robot.rotate(1)
    robot[n-1] = 0

    for i in range(n-2, -1, -1):
        if (robot[i] != 0 and robot[i+1] == 0 and q[i+1] >= 1):
            q[i+1] -= 1
            robot[i+1] = robot[i]
            robot[i] = robot[0]
    robot[n-1] = 0

    if q[0] >= 1:
        q[0] -= 1
        robot[0] = 1
    answer += 1
    if q.count(0) >= k:
        break


print(answer)