BOJ 8090 - 택배(C++)

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

8980번: 택배

 

풀이

입력 값에 대한 정렬이 필요 1. 도착지 오름차순, 2. 출발지 오름차순

해당 지역을 거치는 택배의 총 개수를 저장하는 배열이 필요 -> int capacity[]

* 단 트럭의 용량을 초과할 수는 없음

 

1. 정렬된 배송정보에 대한 탐색

2. 출발지 ~ 도착지중 지역을 거쳐가는 최대의 갯수  max_cnt를 저장

3. 현재 배송지에 대해 가져갈수 있는 택배의 개수를 구함

    - 배송 정보의 택배 갯수가 남은 트럭의 용량 작으면, 트럭의 용량 - max_cnt

    - 충분히 담을 수 있다면, 배송지의 갯수

4. 3에서 구한 값을 출발지 ~ 도착지의 capacity[]에 누적 합, 다음 배송정보에 대해 1로 돌아가서 다시 탐색

 

* 글로 설명하니 이해하기 어려운거 같아서 그림으로 설명

#include <iostream>
#include <algorithm>

using namespace std;

struct info {
    int start, end, cnt;
}arr[10001];
int capacity[10001] = { 0, };

// 입력값 정렬 1. 도착지 오름차순, 2. 출발지 오름차순
bool cmp(info a, info b) {
    if (a.end < b.end)
        return true;
    else if (a.end == b.end) {
        if (a.start < b.start)
            return true;
    }
    return false;
}

int main() {
    int C, N, M;
    int res = 0;
    cin >> N >> C >> M;
    int s, e, c;
    for (int i = 0; i < M; i++) {
        cin >> s >> e >> c;
        arr[i] = info{ s,e,c };
    }
    sort(arr, arr + M, cmp);
    
    // 배송 정보마다 탐색
    for (int i = 0; i < M; i++) {
        int start = arr[i].start;
        int end = arr[i].end;
        int cnt = arr[i].cnt;
        int max_cnt=0;
        
        // 현재 배송 정보의 출발지~도착지-1에서 최대 capacity값
        for (int j = start; j < end; j++) {
            max_cnt = max(capacity[j], max_cnt);
        }
        
        // 현재 배송정보에 대해 가지고 갈 수 있는 갯수
        int val = min(cnt, C - max_cnt);
        res += val;
        
        // 현재 배송 정보의 출발지~도착지-1의 capacity에 val을 더함
        for (int j = start; j < end; j++) {
            capacity[j] += val;
        }
    }

    cout << res;
    return 0;
}