[백준 8980] 택배 (C#, C++) - soo:bak

문제 링크

8980번 - 택배

설명

트럭이 1번 마을에서 출발하여 N번 마을까지 한 방향으로 이동하면서 택배를 배송할 때, 최대로 배송할 수 있는 박스 수를 구하는 문제입니다.

접근법

트럭은 되돌아갈 수 없고, 실은 박스는 도착지에서만 내릴 수 있습니다. 도착지가 가까운 택배를 먼저 처리하면 그 박스가 트럭에 오래 머무르지 않아서, 뒤쪽 구간에서 더 많은 박스를 실을 여유가 생깁니다.

모든 택배 요청을 도착지가 가까운 순서로 정렬합니다. 도착지가 같으면 출발지가 가까운 순서로 정렬합니다.

각 구간별로 현재 트럭에 실린 박스 수를 기록합니다. 택배 요청을 하나씩 처리할 때, 해당 경로의 모든 구간 중 가장 많이 실려 있는 구간을 확인합니다. 트럭 용량에서 그 값을 빼면 추가로 실을 수 있는 양이 됩니다. 요청된 수량과 비교해서 더 작은 만큼만 실어서 배송량에 더하고, 해당 경로의 모든 구간에 적재량을 갱신합니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  struct Req {
    public int From, To, Cnt;
  }

  static void Main() {
    var first = Console.ReadLine()!.Split();
    var n = int.Parse(first[0]);
    var cap = int.Parse(first[1]);
    var m = int.Parse(Console.ReadLine()!);

    var reqs = new List<Req>(m);
    for (var i = 0; i < m; i++) {
      var parts = Console.ReadLine()!.Split();
      reqs.Add(new Req {
        From = int.Parse(parts[0]),
        To = int.Parse(parts[1]),
        Cnt = int.Parse(parts[2])
      });
    }

    reqs.Sort((a, b) => {
      var cmp = a.To.CompareTo(b.To);
      if (cmp != 0) return cmp;
      return a.From.CompareTo(b.From);
    });

    var load = new int[n + 1];
    var delivered = 0;

    foreach (var r in reqs) {
      var maxLoad = 0;
      for (var i = r.From; i < r.To; i++)
        if (load[i] > maxLoad) maxLoad = load[i];

      var take = Math.Min(r.Cnt, cap - maxLoad);
      if (take <= 0) continue;
      delivered += take;
      for (var i = r.From; i < r.To; i++)
        load[i] += take;
    }

    Console.WriteLine(delivered);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

struct Req {
  int from, to, cnt;
};

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

  int n, c; cin >> n >> c;
  int m; cin >> m;
  vector<Req> reqs(m);
  for (auto& r : reqs) cin >> r.from >> r.to >> r.cnt;

  sort(reqs.begin(), reqs.end(), [](const Req& a, const Req& b) {
    if (a.to != b.to) return a.to < b.to;
    return a.from < b.from;
  });

  vi load(n + 1, 0);
  int ans = 0;

  for (const auto& r : reqs) {
    int mx = 0;
    for (int i = r.from; i < r.to; i++) mx = max(mx, load[i]);
    int take = min(r.cnt, c - mx);
    if (take <= 0) continue;
    ans += take;
    for (int i = r.from; i < r.to; i++) load[i] += take;
  }

  cout << ans << "\n";

  return 0;
}