[그리디/백준] 8980번: 택배(다시)

-문제 : https://www.acmicpc.net/problem/8980

 

-정답풀이 :

도착지가 가까운 곳을 기준으로 박스를 싣는다. 

마을 중에서 택배양이 최소인 택배를 싣는 이유는 적게 싣고 빨리 배달해야 후에 더 많은 택배를 실을 수 있기 때문이다. 

택배를 실었을 때 남은 적재량을 저장한다

 

참고한 블로그 : https://javaiyagi.tistory.com/586

n,c=map(int,input().split())
m=int(input())
boxes=[]
arrive=[c]*n

for _ in range(m):
    boxes.append(list(map(int,input().split())))
boxes.sort(key=lambda x : x[1])

answer=0
for i in range(len(boxes)):
    minNum=c+1
    #시작마을,도착마을
    a,b=boxes[i][0],boxes[i][1]    
    for j in range(a,b):
    	#지나가는 마을 중 최소 적재량 찾기
        minNum=min(minNum,arrive[j])
        
    #a마을에서 보낼 적재량과 a와 b사이에 있는 택배중 적은 적재량 비교??
    x=min(minNum, boxes[i][2])
    answer+=x
    for j in range(a,b):
        arrive[j]-=x
       
print(answer)

 

-시도해본 풀이 :

나름 풀어본다고 풀었는데, 계속 틀렸던 풀이다. 

 

n,c=map(int,input().split())
m=int(input())
boxes=[]
for _ in range(m):
    boxes.append(list(map(int,input().split())))
boxes.sort(key=lambda x : x[1])
arrive=[0]*(n+1)
before=[[] for _ in range(n+1)]
for i in range(m):
    x,y,z=boxes[i]
    before[x].append([y,z])
current=0
#처음 트럭에 택배 싣는 경우 
while True:
    if current == c:
        break
    x,y,z=boxes.pop(0)
    if current + z > c:
        arrive[y]=c-current
        current=c        
    else : 
        arrive[y]+=z
        current+=z
        
result=0
for i in range(1,n+1):
    if arrive[i]!=0:
        result+=arrive[i]
        arrive[i]=0
        #i번 마을에 보낼 택배가 있는지 확인
        if len(before[i])!=0:
            for j in range(len(before[i])):
                one,two=before[i][j]
                if sum(arrive)<c:                    
                    if sum(arrive)+two<=c:
                        arrive[one]+=two
                    else:
                        arrive[one]+=(c-sum(arrive))
                                       
print(result)