[백준 32449] Animal Farm (C#, C++) - soo:bak

문제 링크

32449번 - Animal Farm

설명

돼지 한 마리만 선택할 수 있을 때, 다른 동물은 그보다 영향력이 작을 경우에만 포함해 총합을 최대로 만드는 문제입니다.

접근법

돼지를 한 마리 고르면, 영향력이 그보다 작은 다른 동물은 모두 포함하는 것이 최선입니다.

따라서 다른 동물의 영향력을 정렬하고 누적합을 만든 뒤, 각 돼지마다 자신보다 작은 값들의 합을 더해 최댓값을 구합니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var parts = Console.In.ReadToEnd().Split();
    var idx = 0;
    var n = int.Parse(parts[idx++]);

    var pigs = new List<long>();
    var others = new List<long>();

    for (var i = 0; i < n; i++) {
      var species = parts[idx++];
      var val = long.Parse(parts[idx++]);
      if (species == "pig") pigs.Add(val);
      else others.Add(val);
    }

    others.Sort();
    var prefix = new long[others.Count + 1];
    for (var i = 0; i < others.Count; i++)
      prefix[i + 1] = prefix[i] + others[i];

    long best = 0;
    foreach (var p in pigs) {
      var pos = LowerBound(others, p);
      var total = p + prefix[pos];
      if (total > best) best = total;
    }

    Console.WriteLine(best);
  }

  static int LowerBound(List<long> arr, long x) {
    var l = 0;
    var r = arr.Count;
    while (l < r) {
      var mid = (l + r) / 2;
      if (arr[mid] >= x) r = mid;
      else l = mid + 1;
    }
    return l;
  }
}

C++

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

typedef long long ll;
typedef vector<ll> vll;

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

  int n; cin >> n;
  vll pigs, others;
  for (int i = 0; i < n; i++) {
    string s; ll v;
    cin >> s >> v;
    if (s == "pig") pigs.push_back(v);
    else others.push_back(v);
  }

  sort(others.begin(), others.end());
  vll prefix(others.size() + 1, 0);
  for (int i = 0; i < (int)others.size(); i++)
    prefix[i + 1] = prefix[i] + others[i];

  ll best = 0;
  for (ll p : pigs) {
    int pos = lower_bound(others.begin(), others.end(), p) - others.begin();
    ll total = p + prefix[pos];
    if (total > best) best = total;
  }

  cout << best << "\n";

  return 0;
}