Python/백준] 8980 택배

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

8980번: 택배

<문제 해설>

그리디 문제이다.

상자들을 보내는 마을로 heapq를 사용해서 정렬해 받는다.

1. 어떤 마을에 도착했을 때 받을 수 있는 택배 상자를 차에서 내린다.
2. 이제 보낼 상자를 택배에 올려야한다 일단 보내는 마을의 상자는 받아서 택배에 싣는다.
   만약 상자를 넣었는데 최대 용량 초과라면 가장 늦게 주는 마을의 택배량을 초과량만큼 줄인다.
   줄였는데도 초과용량이 남았다면 그다음 늦게 주는마을 줄이는 방식이다

<코드>

import sys
import heapq
N, C = map(int,sys.stdin.readline().split())
M = int(sys.stdin.readline())
sendingBox = []
for m in range(M):
    heapq.heappush(sendingBox,list(map(int,sys.stdin.readline().split())))

cargo = [0]*(N + 1)
lastindex = 0
totalCargo = 0

output = 0
for n in range(1,N+1):
    output += cargo[n]
    totalCargo -= cargo[n]

    while(sendingBox):
        if sendingBox[0][0] == n: ##보내는 마을에 도착한 상자라면
            box = heapq.heappop(sendingBox) ##일단 상자 넣기
            lastindex = max(box[1],lastindex)
            cargo[box[1]] += box[2]
            totalCargo += box[2]
            diff = totalCargo - C
            if diff > 0:
                totalCargo = C
            while diff > 0: ##만약 상자 넣었는데 최대 용량 초과라면 초과량 만큼 가장 늦게 주는 마을 상자부터 하차 !!
                if cargo[lastindex] >= diff:
                    cargo[lastindex] -= diff
                    diff = 0
                    break
                else:
                    diff -= cargo[lastindex]
                    cargo[lastindex] = 0
                    while lastindex > 0: ##lastindex앞으로 움직이기
                        lastindex -= 1
                        if cargo[lastindex] != 0:
                            break
        else:
            break


print(output)

<고찰>

이문제는 사실 고찰때문에 적었다. 나름 구상해서 이번 마을에 택배를 얼만큼 싣을 수 있는지 또 어떤 보내는 택배들을 포기해야 하는지 각 마을에서 계산해 주는 방식으로 구했다.

문제를 풀고 나서 다른사람들의 코드를 보니 마을에서 계산하는 것이 아니라 도착하는 마을로 정렬해서 한 마을에서 최대로 받을 수 있는 택배를 변경해 주는 식으로 진행하는 거 같다.

다른 분들의 코드를 보니 들리지 않아도 되는 마을을 굳이 들릴 필요 없이 계산하는 방식이 있는거 같다 나의 코드는 들릴 필요가 없는 마을로 들리기 때문에 시간적인 손해를 좀더 보는거 같다.

 

앞으로 이런 출발, 도착에 관한 문제는 도착을 정렬해보는 방향으로 구해봐야 할거 같다.