[백준, C++] 8980번 택배

문제

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

 

해설

문제를 다른 시각으로 해석하면 이해하기 수월해지는 문제입니다.

보내는 마을 -> 막대의 시작 지점

받는 마을 -> 막대의 끝 지점

박스 개수 -> 막대의 단위 길이당 무게

마을 -> 지지축 (허용 가능한 최대 무게 = C)

 

예를 들어, C=100이고, '1번마을에서 3번마을로 50개의 박스를 보낸다'를 바꿔서 해석하면 '1번 지지축에서 2번 지지축에 걸쳐있는 막대의 무게는 100이다. 따라서 1번 지지축과 2번 지지축이 각 50의 무게를 부담한다.'입니다.

(1번 지지축에서 3번 지지축이 아닌 이유는 받는 마을(막대의 끝)에서는 트럭에서 박스(단위 길이당 무게)를 하차하기 때문)

 

위를 이해하고나면 이 문제는 N개의 지지축 위에 최대한 막대를 빈틈없이 올리는 방법을 구하는 문제로 바뀝니다.

다시 말해, 막대를 최대한 빼곡하게 지지축 위에 올리는 방법을 구하면 됩니다.

 

막대는 정렬을 통해 기준을 잡고 한 쪽에서부터 차곡차곡 채워야 최대한 빼곡하게 채울 수 있습니다. 이는 아래의 반례를 통해 이해할 수 있습니다.

5 40
3
1 3 40
3 5 40
2 4 40

정답: 80

막대를 뚜렷한 기준 없이 채울 시, 위 예시에 (2 4 40)의 막대가 제일 먼저 채워지는 경우가 생길 수 있습니다.

그렇게 되면 (2 4 40)막대가 없다면, (1 3 40)막대와 (3 5 40)막대를 채워 더 빼곡하게 채울 수 있음에도 불구하고 그럴 수 없게됩니다.

 

이제 앞서 언급한 정렬 방식을 정하고 알고리즘을 구현하면 됩니다.

저는 도착 시간(막대의 끝 지점) 기반으로 정렬하여 왼쪽에서부터 차근차근 채워나가는 방식을 사용했습니다.

 

정답 코드

#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <algorithm>

using namespace std;

struct goodsInfo {
    int departure;
    int arrival;
    int count;
};

struct cmp {
    bool operator() (goodsInfo a, goodsInfo b) {
        return a.arrival != b.arrival
        ? a.arrival < b.arrival
        : a.departure < b.departure;
    }
};

int N, C, M;
vector<goodsInfo> goodsInfos;
int answer;
vector<int> goodsWeightForEachVillage;

void input() {
    cin >> N >> C >> M;
    answer = 0;
    goodsWeightForEachVillage = vector(N + 1, 0);

    int departure, arrival, count;
    for (int i = 0; i < M; i++) {
        cin >> departure >> arrival >> count;
        goodsInfos.push_back({departure, arrival, count});
    }
}

void solution() {
    sort(goodsInfos.begin(), goodsInfos.end(), cmp());

    for (int i = 0; i < M; i++) {
        int enableCapacity = 10001;
        for (int j = goodsInfos[i].departure; j < goodsInfos[i].arrival; j++) {
            enableCapacity = min(enableCapacity, C - goodsWeightForEachVillage[j]);
        }

        for (int j = goodsInfos[i].departure; j < goodsInfos[i].arrival; j++) {
            goodsWeightForEachVillage[j] += min(enableCapacity, goodsInfos[i].count);
        }
        answer += min(enableCapacity, goodsInfos[i].count);
    }
}

void output() {
    cout << answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    input();

    solution();

    output();
}