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

 

---

 

문제

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

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

 

풀이

 

문제 지문이 워낙 이해하기 힘들었다. 심지어 이해를 잘못한 상태로 코드를 짜다가, 영 이상한 거 같아서 질문게시판에서 지문에 대한 설명을 조금 도움 받은 후 풀이했다. pypy3으로 통과했다.

 

 난 총3개의 저장소를 사용해서 풀이했다.

1. (deque) location[i] = i번째 위치에 존재하는 발판
   1. location의 i는 위치적인 면을 나타낸다. 컨베이어는 계속 돌아간다. 1번째 위치는 고정되나, 발판은 계속 변경될 것이다. 따라서 i번째 위치에 어떤 발판이 있는는지 저장한다. 또한 돌아가는 상태는 마지막값을 빼고 첫번째 값에 넣어주면 된다. 따라서 덱을 사용했다.
2. (dictionary) durable[발판번호] = [남은 내구성, 로봇 여부]
   1. 발판의 내구성과 로봇을 저장하는 딕셔너리이다. 보통 durable[location[i]]와 같이, 위치를 location으로 접근하고, 세부적인 값을 얻어내는데 사용한다.
3. (deque) robots => 앞에있는 로봇일수록 빨리 올라온 로봇(먼저 이동해야하는 로봇)
   1. 로봇은 올라온 순서대로 이동이 이루어져야한다. 또한 내릴때(컨베이어에서 없어질떄) 삭제되어야 하기에 두 부분 모두 용이한 덱을 사용했다.

이후에는 순서대로 구현해주면 된다.

1. 벨트의 회전
   
   1. 오른쪽에서 값을 빼낸 후에, 왼쪽으로 넣어주면 끝이다.
   2. 단, 한칸씩 이동하면서 n번째 발판에 로봇이 존재한다면 제거해줘야한다.
2. 로봇 한칸씩 이동
   1. 올라온 순서대로 저장되어있는 robots 를 하나씩 pop해주면서 검사한다. 만약 이동할려는 칸이 내구도가 없거나 이미 로봇이 존재한다면, 이동할 수 없기에 다시 append 해주면 된다.
      만약 이동할경우에는 우선 현재 위치의 로봇상태를 없다는것으로 갱신해주고, 다음칸의 내구도를 한 칸 깎아주어야 한다. 또한 마지막 칸일 경우에는 로봇을 제거해주면 되고, 아니라면 상태를 갱신해주면 된다.
3. 새로운 로봇을 올려준다.
   1. 첫번째 칸의 내구도가 0이 아니라면 올려주고 상태를 갱신해주면 된다.

코드

from sys import stdin
from collections import deque

def getNext(v):
    global n
    if v == n*2-1:
        return 0
    return v+1

n, k = map(int, input().split())

robots = deque()
location = deque()
for i in range(2*n):
    location.append(i)

durable = {}
temp = list(map(int, stdin.readline().rstrip().split()))
for i in range(n*2):
    durable[i] = [temp[i], False]
turn = 0
while True:
    cnt = 0
    for l in location:
        if durable[l][0] == 0:
            cnt+=1
    if cnt >= k :
        break

    # 벨트 회전 한다.
    location.appendleft(location.pop())
    # n번째 위치 발판에 로봇이 있다면 삭제해준다.
    if durable[location[n-1]][1]:
        durable[location[n-1]][1] = False
        robots.popleft()

    # 벨트에 올라온 순서대로 한칸씩 이동시켜준다.
    l = len(robots)
    for i in range(l):
        val = robots.popleft()
        nxt = getNext(val)
        # 다음칸의 내구도가 존재하면서, 로봇이 없을 경우 -> 다음칸으로 이동이 가능하다.
        if durable[nxt][0] != 0 and not durable[nxt][1]:
            #다음칸이 내리는곳이라면

            if nxt == location[n-1]:
                pass
            else:
                durable[nxt][1] = True
                robots.append(nxt)

            durable[val][1] = False
            durable[nxt][0] -= 1
        # 만약 이동하지 못하면 그대로 둔다.
        else:
            robots.append(val)

    # 올리는 발판에 로봇이 없다면 올려준다.
    if durable[location[0]][0] != 0 :
        robots.append(location[0])
        durable[location[0]][0] -= 1
        durable[location[0]][1] = True

    turn+=1

print(turn)

 

후기

 

처음에 문제 이해를 잘못해서 조금 어렵게 짠 거 같기도 하다. 인덱스 값으로 배열값을 넣는건 너무 헷갈려서 조금만 잘못해도 틀리기 때문에..