8980번 택배

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

어려웠다.

처음에는 단순 3개(f, t, c)에 대한 오름차순으로 sort를 하여, 구현하였으나 틀렸다.

알고보니, 

도착지를 기준으로 오름차순하면 됐었다.

도착지가 같을 경우 출발지 기준으로 오름차순.

즉, 출발지 상관없이, 도착지가 무조건 1에 가까운 순서대로 sort를 한다.

하지만 나는 sort를 한 후에도 구현을 제대로 못 했었다.

핵심은 sort를 한 후에

vector v에 담겨져 있는 순서대로 해당 인덱스의 v에 대한 f ~ t - 1 까지

현재 싣고 있는 택배 개수의 최댓값을 구한다.

이유는 어차피 최댓값을 기준으로 실을 수 있는 택배가 결정되기 때문이다.

그 다음,

실을 수 있는 택배 개수( = (제한 택배 개수) - (위에서 구한 최댓값) )

와

해당 출발지(i.f)에서 요청한 택배 개수( = i.c = b) 

중에서 최솟값을 구한다.

그리고 이 구한 최솟값을 answer(답)에 누적하여 더한다.

그리고 구한 최솟값을

t[i.t - 1]에 누적하여 더한다.

t[i.t]가 아닌 이유는 어차피 i.t지점에서 해당 택배들은 보내기 때문이다.

t[x] : x번 지점에 대한 트럭에 현재 싣고 있는 택배의 개수

#include <bits/stdc++.h>
 
using namespace std;
 
typedef struct info
{
    int f, t, c;
}info;
 
int n, c, t[2002];
 
vector<info> v;
 
// 또는 애초에, t를 맨 앞으로 하여, cmp 함수를 사용하지 않아도 된다.
bool cmp(const info & a, const info & b)
{
    if (a.t == b.t) return a.f < b.f;
    else return a.t < b.t;
}
 
int main(void)
{
    int m, from, to, capacity, answer = 0, burden = 0;
 
    scanf("%d %d %d", &n, &c, &m);
 
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &from, &to, &capacity);
        v.push_back({ from, to, capacity });
    }
 
    sort(v.begin(), v.end(), cmp);
 
    for (auto i : v)
    {
        int burden = 0, b = i.c;
 
        for (int j = i.f; j < i.t; j++)
            burden = max(burden, t[j]);    
 
        burden = min(c - burden, b);
        answer += burden;
 
        for (int j = i.f; j < i.t; j++)
            t[j] += burden;
    }
 
    printf("%d\n", answer);
 
    return 0;
}