[BOJ] 8980

문제

me

1차시: 정렬을 그냥 순서대로 했다. 또, 칸마다 배달 할 수 있도록 [0]*(N+1)을 하여 정리했다.
2차시: 정렬을 도착 순서대로 해야하는 것은 알았다. 다만, 그 뒤에 방법을 모르겠다.

solution

import sys

if __name__ == "__main__":
    n, c = map(int, sys.stdin.readline().split())
    m = int(sys.stdin.readline())
    box = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]


    box.sort(key=lambda x:x[1])  # 도착 시간이 빠른 순서로 정렬

    answer = 0  # 최대 박스 수
    remain = [c] * (n + 1)  # 각 위치에 남은 공간

    for i in range(m):
        temp = c  # c개를 옮길 수 있다고 가정
        for j in range(box[i][0], box[i][1]):
            temp = min(temp, remain[j])
        temp = min(temp, box[i][2])
        for j in range(box[i][0], box[i][1]):
            remain[j] -= temp
        answer += temp

    print(answer)

1. 도착 순서가 빠른 순서로 박스를 정렬합니다.
2. 마을의 수와 길이가 동일한 배열을 선언합니다. (초기값은 트럭의 최대 용량입니다)
3. 현재 박스의 출발 위치에서 도착 위치로 배송할 수 있는 만큼 최대한 박스를 배송합니다.
   • 2번에서 선언한 배열에는 각 위치에 배송할 수 있는 최대 박스 크기가 저장되어 있습니다. 따라서 출발 위치에서 도착 위치 사이에 있는 배열의 값 중 가장 작은 값과 현재 배송할 박스의 수 중 작은 값을 최종적으로 배송할 수 있습니다.

지금 차례의 박스의 출발부터 도착까지 옮길 수 있는 양을 찾고,
그 양과 현재 박스의 양 중에 고르고
그거 만큼 출발에서 도착까지 이동량을 조절,,
수용 가능 박스량을 누적하여 기록하는 것..

참고