백준: 8980 택배

문제

8980번: 택배

 

문제 풀이

 접근법을 생각하기까지 시간이 걸렸으며, 다소 어려웠다. 문제의 해답은 각 마을 별로 출발지 도착지를 기준으로 출발 가능한 양을 지속적으로 확인해야 한다는 것이다.

 

• 마을 별로 실을 수 있는 최대 박스의 양을 트럭의 용량으로 초기화한다.
• 입력된 값을 도착지를 기준으로 정렬한다
• 입력된 값을 순차적으로 돌며, 출발지 도착지에 적재 가능량과 박스의 양을 비교하여 처리한다.
• 이를 순차적으로 반복하면 요구하는 답을 찾을 수 있다.

 

코드

from sys import stdin

if __name__ == "__main__":
    N, C = map(int, stdin.readline().split())
    M = int(stdin.readline())
    info = sorted([list(map(int, stdin.readline().split())) for _ in range(M)], key= lambda x: x[1])

    answer = 0
    village = [C] * N

    for start, end, box in info:
        # list 인덱스에 맞게 변환
        start -= 1
        end -= 1

        # 최소 적재량 선택
        load = min(village[start:end])

        if not load:
            continue

        # 적재 가능한 양보다 큰 경우, 적재 가능한 양만
        send = box if box <= load else load

        for idx in range(start, end):
            village[idx] -= send

        answer += send

    print(answer)