[백준 16770] The Bucket List (C#, C++) - soo:bak

문제 링크

16770번 - The Bucket List

설명

여러 소가 겹치는 시간 동안 사용하는 버킷 수의 합이 필요 최소 버킷 수가 되는 문제입니다.

접근법

각 소의 시작 시각에는 버킷 수를 더하고, 종료 시각에는 버킷 수를 뺀다고 생각합니다. 시간별 누적합을 계산하면서 최댓값을 구하면 필요한 총 버킷 수가 됩니다. 시간은 1부터 1000까지이므로 차이 배열로 쉽게 처리할 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var diff = new int[1002];

    for (var i = 0; i < n; i++) {
      var parts = Console.ReadLine()!.Split();
      var s = int.Parse(parts[0]);
      var t = int.Parse(parts[1]);
      var b = int.Parse(parts[2]);
      diff[s] += b;
      diff[t] -= b;
    }

    var cur = 0;
    var best = 0;
    for (var time = 1; time <= 1000; time++) {
      cur += diff[time];
      if (cur > best) best = cur;
    }

    Console.WriteLine(best);
  }
}

C++

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

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

  int n; cin >> n;
  vector<int> diff(1002, 0);

  for (int i = 0; i < n; i++) {
    int s, t, b; cin >> s >> t >> b;
    diff[s] += b;
    diff[t] -= b;
  }

  int cur = 0, best = 0;
  for (int time = 1; time <= 1000; time++) {
    cur += diff[time];
    if (cur > best) best = cur;
  }

  cout << best << "\n";

  return 0;
}