[백준] 8980번 택배 (파이썬)

난이도 : GOLD II

문제링크 : https://www.acmicpc.net/problem/8980

문제해결 아이디어

• 그리디 알고리즘이다.
• 처음에는 시작점, 도착점을 기준으로 정렬을 했는데 도착점만을 기준으로 정렬을 해야했다.
• 1->5를 먼저하면 2->3, 3->4 와 같은 애들은 못할 수 있기 때문이다.

소스코드

import sys

input = sys.stdin.readline

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

k = int(input())
town = []
for _ in range(k):
  #보내는 마을, 받는 마을, 박스 개수
  town.append(list(map(int,input().split())))

town.sort(key=lambda x:x[1])

box = [w] * (n+1)

total = 0

for s,e,b in town:
  _min = b
  for i in range(s,e): #싣을 수 있는 무게 구하기 # box[e] 는 어차피 다시 더해야 하므로 포함x
    _min = min(_min, box[i])

  for i in range(s,e): #모든 마을 box 무게 변경
    box[i] -= _min

  total += _min

print(total)