문제 A: 사과 구매

기본적인 나눗셈 연산을 통해 해결할 수 있는 간단한 문제입니다.

n, x = map(int, input().split())
result = n // x
print(result)

문제 B: 소의 분류

문자열의 빈도수를 기준으로 다양한 경우의 수를 분석해야 합니다.

from collections import Counter

data = input().strip()
frequency = sorted(Counter(data).values())
length = len(frequency)

if length >= 5:
    print("No")
elif length == 4:
    print("Yes")
elif length == 3:
    max_freq = frequency[-1]
    print("Yes" if max_freq >= 2 else "No")
elif length == 2:
    print("Yes" if all(freq >= 2 for freq in frequency) else "No")
else:
    print("No")

문제 C: 운송 회사 최적화

이 문제는 제한 조건 하에서 최대 이익을 얻기 위한 1:1 매칭 문제로, 반悔 힙(后悔堆) 그리디 기법이 효과적으로 적용됩니다. 네트워크 플로우로도 해결 가능하지만, 반悔 힙 접근이 더 일반적입니다.

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

struct Truck {
    int profit, weight, id;
    bool operator<(const Truck& other) const {
        return profit < other.profit;
    }
};

struct Order {
    int price, id;
    bool operator<(const Order& other) const {
        return price < other.price;
    }
};

struct Match {
    int gain, truck_id, order_id;
};

struct MatchCompare {
    bool operator()(const Match& a, const Match& b) const {
        return a.gain > b.gain;
    }
};

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

    int truck_count;
    cin >> truck_count;
    
    vector<Truck> trucks(truck_count);
    for (int i = 0; i < truck_count; i++) {
        int p, w;
        cin >> p >> w;
        trucks[i] = {p, w, i + 1};
    }
    sort(trucks.rbegin(), trucks.rend());

    int order_count;
    cin >> order_count;
    vector<Order> orders(order_count);
    for (int i = 0; i < order_count; i++) {
        cin >> orders[i].price;
        orders[i].id = i + 1;
    }
    sort(orders.rbegin(), orders.rend());

    priority_queue<Match, vector<Match>, MatchCompare> heap;
    long long total_profit = 0;
    int order_index = 0;

    for (const auto& truck : trucks) {
        if (order_index < order_count && truck.profit <= orders[order_index].price) {
            heap.push({truck.weight, truck.id, orders[order_index].id});
            total_profit += truck.weight;
            order_index++;
        } else if (!heap.empty() && truck.weight > heap.top().gain) {
            auto current = heap.top();
            heap.pop();
            total_profit = total_profit - current.gain + truck.weight;
            heap.push({truck.weight, truck.id, current.order_id});
        }
    }

    cout << heap.size() << " " << total_profit << "\n";
    vector<pair<int, int>> results;
    while (!heap.empty()) {
        auto match = heap.top();
        heap.pop();
        results.push_back({match.truck_id, match.order_id});
    }
    sort(results.begin(), results.end());
    for (auto& result : results) {
        cout << result.first << " " << result.second << "\n";
    }

    return 0;
}