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

1. 문제 링크

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

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

 

2. 문제 요약

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

* 로봇은 올리는 위치에만 올리기 가능 
* 언제든지 n(내리는 위치)에 있으면 바로 내림 
* 로봇은 컨베이어벨트 위에서는 스스로 이동 가능 
* 로봇을 올리는 위치에 올리거나 어떤 칸으로 이동 시 그 칸 내구도는 -1 

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

 

3. 아이디어 정리

 

• 회전을 쉽게 하기 위해 deque를 사용한다.
• n개의 벨트만 로봇이 존재할 수 있음 ⇒ n길이의 로봇 유무를 저장하는 배열을 만든다.

1. 벨트를 회전한다. ⇒ deque rotate사용
2. 로봇 이동하기
   1. 가장 먼저 올라간 로봇부터 앞으로 이동
   2. 다음칸이 내구도 존재하고, 로봇도 없고, 현재 로봇이 존재하는 경우 진행
3. 올리는 위치에 내구도 0이 아니고, 로봇이 처음에 존재하지 않으면 로봇 올리기
4. 내구도 0인 칸 수가 k이상이면 그만

4. 문제 풀이

4-1. 내 풀이

from collections import deque

n, k = map(int, input().split())
a = deque(map(int, input().split()))  # 내구도. A1, A2, ..., A2N
robot = deque([0] * n)  # 벨트위에 있는 로봇
result = 0

while True:
    result += 1
    # 1. 벨트 회전한다.
    a.rotate(1)
    robot[-1] = 0
    robot.rotate(1)
    robot[-1] = 0    # 내리는 위치에 도달한 경우, 즉시 내림
    # 2. 로봇 이동하기. 이동하려는 칸에 로봇 x, 내구도 1이상 남아야함.
    for i in range(n - 2, -1, -1):  # 먼저 올라간 로봇부터 진행
        if a[i + 1] >= 1 and robot[i + 1] == 0 and robot[i] == 1:
            robot[i + 1] = 1
            robot[i] = 0
            a[i + 1] -= 1
    robot[-1] = 0  # 내리는 위치에 도달한 경우, 즉시 내림
    # 3. 올리는 위치에 내구도 0 아니면 로봇 올리기 & 내구도 감소
    if a[0] != 0 and robot[0] != 1:
        robot[0] = 1
        a[0] -= 1
    # 4. 내구도 0인 칸 수가 k이상이면 종료
    if a.count(0) >= k:
        break
print(result)

5. 결론 및 느낀 점

• 이해하기가 어려웠던 문제