[백준] 13335번 트럭 (Python)

문제 출처

ICPC Regionals Asia Pacific Korea Daejeon Nationalwide Internet Competition 2016 L번

문제 주소

백준 13335번 트럭

13335번: 트럭

문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단��

www.acmicpc.net

알고리즘

Queue

힌트

다리가 무게가 0인 트럭들로 꽉 차있다고 생각하고 문제를 푼다

문제풀이

truck큐와 bridge큐를 만들어서 다리 위에 있는 트럭들과 대기중인 트럭들을 관리한다.

class ArrayQueue:
  def __init__(self):
    self.data = []

  def size(self):
    return len(self.data)

  def isEmpty(self):
    return self.size()==0

  def enqueue(self, item):
    self.data.append(item)

  def dequeue(self):
    if self.isEmpty():
      print("빈 큐임")
    else:
      return self.data.pop(0)

  def peek(self):
    if self.isEmpty():
      print("빈 큐임")
    else:
      return self.data[0]

a=input().split(" ")
tmp = input().split(" ")

truck = ArrayQueue()
time=0
bridge = ArrayQueue()
birdsum=0

for i in tmp:
    truck.enqueue(int(i))
for i in range(int(a[1])):
    bridge.enqueue(0)

while not bridge.isEmpty():

    if truck.isEmpty():
        bridge.dequeue()

    else:
        birdsum-=bridge.dequeue()

        if birdsum+truck.peek() <= int(a[2]):
            tmp=truck.dequeue()
            birdsum+=tmp
            bridge.enqueue(tmp)
        else :
            bridge.enqueue(0)
    time+=1
    #print("truck\n",truck.data)
    #print("bridge\n",bridge.data)

print(time)