1. Cow College - 최대 수익 구하기

Farmer John이 소들을 위한 대학을 세우려고 한다. N마리의 소(1 ≤ N ≤ 10^5)가 있으며, 각 소는 최대 c_i(1 ≤ c_i ≤ 10^6)만큼의 학비를 낼 의향이 있다. 등록금을 책정했을 때, 소가 지불할 수 있는 최대 금액보다 높으면 해당 소는入学하지 않는다. FJ는 최대 수익을 얻고자 하며, 그때의 등록금을 구해야 한다. 여러 답이 있다면 가장 작은 등록금을 출력한다.

접근 방법: 소들이 지불 가능한 금액을 정렬한 후, 각 금액을 등록금으로 설정했을 때의 수익을 계산한다. 정렬된 배열에서 i번째 요소를 등록금으로 하면, (N - i + 1)마리의 소가 등록한다. 따라서 수익 = a[i] * (N - i + 1)이다. 최대 수익을 갱신하며 최소 등록금을 찾는다.

시간 복잡도는 O(N log N) (정렬 포함)이다.

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

int main() {
    long long N;
    cin >> N;
    vector<long long> cows(N);
    for (int i = 0; i < N; ++i) cin >> cows[i];
    sort(cows.begin(), cows.end());

    long long max_profit = 0, best_tuition = 0;
    for (int i = 0; i < N; ++i) {
        long long profit = cows[i] * (N - i);
        if (profit > max_profit) {
            max_profit = profit;
            best_tuition = cows[i];
        }
    }
    cout << max_profit << " " << best_tuition << "\n";
    return 0;
}

2. Feeding the Cows - 목초지 최소 배치

N마리의 소가 일렬로 서 있고, 각 소는 G(건지) 또는 H(홀스타인) 품종이다. FJ는 1부터 N까지의 위치에 목초지를 심을 수 있으며, 한 위치에는 한 가지 품종만 먹일 수 있다. 각 소는 최대 K(0 ≤ K ≤ N-1) 거리 이내의 목초지로 이동 가능하다. 모든 소를 먹이기 위해 필요한 최소 목초지 개수와 배치 방법을 구한다.

접근 방법: 탐욕법을 사용한다. 각 소를 왼쪽에서 오른쪽으로 확인하며, 아직 먹이를 못 먹은 소가 있으면 그 위치에서 K만큼 떨어진 곳(i + K)에 해당 품종의 목초지를 심는다. 만약 i + K가 N을 초과하면, 빈 자리 중 가장 오른쪽에 심는다. 목초지를 심은 후에는 해당 품종의 소가 영향을 받는 범위(i + 2K)까지 건너뛴다.

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, K;
        string s;
        cin >> N >> K >> s;
        vector<char> pasture(N, '.');
        int cnt = 0;
        int last_G = -1, last_H = -1;

        for (int i = 0; i < N; ++i) {
            if (s[i] == 'G' && i > last_G) {
                int pos = min(i + K, N - 1);
                while (pasture[pos] != '.') --pos;
                pasture[pos] = 'G';
                ++cnt;
                last_G = pos + K;
            } else if (s[i] == 'H' && i > last_H) {
                int pos = min(i + K, N - 1);
                while (pasture[pos] != '.') --pos;
                pasture[pos] = 'H';
                ++cnt;
                last_H = pos + K;
            }
        }
        cout << cnt << "\n";
        for (char c : pasture) cout << c;
        cout << "\n";
    }
    return 0;
}

3. Reverse Engineering - 프로그램 검증

Elsie가 N개의 0/1 입력을 받아 0 또는 1을 반환하는 if-else if-else 프로그램을 만들었다. 각 조건문은 하나의 입력 변수만 확인한다. Bessie는 M개의 입력-출력 쌍을 알고 있으며, 이와 일치하는 프로그램이 존재하는지 판단해야 한다. 존재하면 "OK", 없으면 "LIE"를 출력한다.

접근 방법: 가능한 변수와 값을 하나씩 제거하는 방식으로 검증한다. 현재 남아 있는 입력들 중에서, 특정 변수의 특정 값(0 또는 1)이 항상 같은 출력을 내는 조건이 있다면 그 분기를 확정하고 해당 조건을 만족하는 입력을 제거한다. 이 과정을 더 이상 분기를 찾을 수 없을 때까지 반복한다. 최종적으로 모든 입력이 제거되면 OK, 그렇지 않으면 LIE이다.

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;
        vector<string> inputs(M);
        vector<int> outputs(M);
        for (int i = 0; i < M; ++i) cin >> inputs[i] >> outputs[i];

        vector<bool> removed(M, false);
        vector<bool> used_var(N, false);
        bool changed = true;
        while (changed) {
            changed = false;
            for (int v = 0; v < N; ++v) {
                if (used_var[v]) continue;
                int count[2][2] = {{0,0},{0,0}}; // [value][output]
                for (int i = 0; i < M; ++i) {
                    if (removed[i]) continue;
                    int val = inputs[i][v] - '0';
                    int out = outputs[i];
                    count[val][out]++;
                }
                // check if this variable with a specific value always leads to same output
                if ((count[0][0] == 0 && count[0][1] > 0) || (count[0][1] == 0 && count[0][0] > 0)) {
                    changed = true;
                    used_var[v] = true;
                    for (int i = 0; i < M; ++i) {
                        if (!removed[i] && inputs[i][v] == '0') removed[i] = true;
                    }
                }
                if ((count[1][0] == 0 && count[1][1] > 0) || (count[1][1] == 0 && count[1][0] > 0)) {
                    changed = true;
                    used_var[v] = true;
                    for (int i = 0; i < M; ++i) {
                        if (!removed[i] && inputs[i][v] == '1') removed[i] = true;
                    }
                }
            }
        }
        bool all_removed = true;
        for (bool r : removed) if (!r) all_removed = false;
        cout << (all_removed ? "OK" : "LIE") << "\n";
    }
    return 0;
}