컨베이어 벨트 위의 로봇

알고리즘

• 시뮬레이션

구현 방법

• 컨베이어 벨트를 위,아래로 나눔 (덱 이용) / 로봇 위치 (덱 이용)

• 로봇 옮기는 작업

  • 회전

    • 컨베이어 벨트 회전

      • 덱 이용

    • 로봇도 같이 회전

      deq.rotate(1) # 인덱스를 한칸씩 민다.
      deq.rotate(-1) # 인덱스를 한칸씩 당긴다.

• 이동

  • 맨 마지막 로봇 내리기
  • 중간에 있는 로봇 이동
  • 맨 앞에 로봇 올리기

• 체크

잘못된 접근

• 로봇이 어떤 칸에 올라가거나 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다.
  • 처음 생각했던 것은 이동하려는 칸의 내구도 감소 + 기존에 있던 칸의 내구도 감소로 이해
  • 정답은 이동하려는 칸의 내구도만 감소

시간 복잡도

O(n)

• N이 최대 100이고, 모든 내구도가 1000이면 => 1단계에 내구도 1 떨어짐
  • 2 100 1000 = 20만이므로 시간초과 나지 않음

코드

from _collections import deque


def check_zero(deq,c):
    for v in deq:
        if not v:
            c += 1
    return c


N,K = input().split()
N,K = int(N), int(K)
arr = list(map(int,input().split()))
U,D = deque(arr[:N]),deque(arr[2*N-1:N-1:-1])
robot = deque([0]*N)
cnt = check_zero(U,0)
cnt = check_zero(D,cnt)
count = 0
while cnt < K:
    count += 1
    # 회전
    D.append(U.pop())
    U.appendleft(D.popleft())
    robot.rotate(1)
    robot[0] = 0
    # 이동
    robot[-1] = 0 # 로봇 내림
    for i in range(N-2,-1,-1):
        if robot[i] and not robot[i+1] and U[i+1]:
            U[i+1] -= 1
            robot[i+1] = 1
            robot[i] = 0
            # U[i] -= 1
    # 로봇 올림
    if U[0]:
        U[0] -= 1
        robot[0] = 1
    cnt = check_zero(U,0)
    cnt = check_zero(D,cnt)

print(count)