백준 8980 택배 Python3

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

8980번: 택배

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ8980.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

N, C = map(int, input().split())
M = int(input())
box_info = []
truck_capa = [C]*(N+1)
for _ in range(M):
    box_info.append(list(map(int, input().split())))
box_info.sort(key = lambda x:x[1])
b_cnt = 0
for i in range(M):
    min_box = C
    for town in range(box_info[i][0], box_info[i][1]):
        if truck_capa[town] < min_box: min_box = truck_capa[town]
    min_box = min(min_box, box_info[i][2])
    b_cnt += min_box
    for town in range(box_info[i][0], box_info[i][1]):
        truck_capa[town] -= min_box
print(b_cnt)

---

풀이 과정

N, C = map(int, input().split())
M = int(input())

#box_info[i] = [보낸 마을 번호, 받는 마을 번호, 박스수]
box_info = []
#truck_capa[i] = 마을 i에서 트럭의 수용 가능한 박스 수
truck_capa = [C]*(N+1)

for _ in range(M):
    box_info.append(list(map(int, input().split())))
    
#받는 마을 번호가 빠른 순으로 박스 정보를 정렬
box_info.sort(key = lambda x:x[1])

#배송한 박스 수
b_cnt = 0
for i in range(M):
	#보낸 마을에서 받는 마을에 도착할 때까지 트럭을 운행하면서 배송할 박스 수
    #가능한 작은 박스 수를 배송해야 하기 때문에 최대인 C로 초기화
    min_box = C
    
    #보낸 마을부터 받는 마을의 이전 마을까지 트럭의 수용가능한 박스 수를 구한다
    #truck_capa[보낸 마을]~truck_capa[받는 마을-1] 중 가장 작은 값을 min_box로 선택해야 트럭 용량을 초과하지 않는다
    for town in range(box_info[i][0], box_info[i][1]):
        if truck_capa[town] < min_box: min_box = truck_capa[town]
        
    #현재 박스 정보의 박스 수 <= min_box인 경우 해당 박스 수만큼 트럭에 실는다
    #현재 박스 정보의 박스 수 > min_box인 경우 해당 박스 수의 일부만(min_box만큼) 트럭에 실는다
    min_box = min(min_box, box_info[i][2])
    b_cnt += min_box
    
   	#보낸 마을부터 받는 마을의 이전 마을까지 운송해야하므로 트럭 수용 가능 수를 min_box만큼 빼준다
    for town in range(box_info[i][0], box_info[i][1]):
        truck_capa[town] -= min_box
print(b_cnt)
#시간복잡도 = O(M*N), 공간복잡도 = O(M)