택배 (8980번) - 백준 (BOJ)

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

8980번: 택배

 

 

백준 - 택배 (8980번)

 

난이도 : Gold 2

알고리즘 : Sorting

풀이 소요 시간 : 100 mins

Time Complexity : O(N^2)   ( O( N*logN ) 도 가능 )

 

import sys
input = sys.stdin.readline


if __name__ == '__main__':
    N, C = map(int, input().split())
    M = int(input())
    ts = [tuple(map(int, input().split())) for _ in range(M)]
    ts.sort(key=lambda x: x[1])
    
    tree = [0] * (N+1)
    ans = 0
    for s, r, v in ts:
        _max = max(tree[s:r])
        if _max == C:  continue
        free = C - _max
        load = min(free, v)
        ans += load
        for i in range(s, r):
            tree[i] += load
    print(ans)

 

Segment Tree 로 풀어보려다가 시간만 잡아먹었다.

 

특정 구간에 어떤 값을 더해주는 것 까지는 세그먼트 트리로 가능했지만,

그 구간에서 최댓값을 가져오는 기능도 동시에 구현해야 했기에

결과적으로 segment tree를 적용할 수 없었다.

 

세그먼트 트리는 포기하고, 그냥 정렬 후 순차 탐색으로 풀어봤는데

O(N^2) 으로 풀어도 충분히 시간 안에 풀 수 있는 문제였다.

 

다른 사람들의 풀이를 보니,

우선 순위 큐를 통해서 O( N*logN ) 으로 푸는 것도 가능해보인다.

 

---

 

<풀이 과정>

 

1. 택배를 도착지 기준으로 정렬

2. 현재 택배의 출발지부터 도착지까지의 기록 중에서, 가장 많은 택배를 싫은 값 찾기

3. 2 번에서 찾은 값에 얹어서, 택배 트럭에 가능한 한 최대한 많이 올림

4. 3번에서 추가한 값, 현재 택배 출발지부터 도착지까지 기록에 모두 더함

5. 2~4번 반복

6. 배달한 택배 양 반환