USACO 2023 1월 콘테스트의 브론즈 문제를 다룹니다.

문제 1: 지도자들

농부 존은 N 마리의 소들을 가지고 있으며(2≤N≤10^5), 각각의 소는 Guernsey 또는 Holstein 중 하나로 구분됩니다. 소들은 1번부터 N번까지 줄을 서 있습니다. 하루 동안 각 소는 자신부터 Ei 번째 소까지의 범위를 포함하는 리스트를 작성합니다(i≤Ei≤N). 존은 최근에 각 품종마다 단 한 명의 리더가 있다는 사실을 알게 되었습니다. 그는 각 리더가 자신의 품종에 속한 모든 소들의 리스트를 포함하거나, 다른 품종의 리더를 포함하고 있다고 추측합니다. 이 두 가지 조건 중 하나만 충족해도 리더로 간주됩니다. 가능한 리더 쌍의 수를 계산하세요. 적어도 한 개의 가능한 쌍이 존재함이 보장됩니다.

입력 형식: 첫 번째 줄에는 N이 주어집니다. 두 번째 줄에는 길이 N의 문자열이 주어지며, i번째 문자는 i번째 소의 품종(G는 Guernsey, H는 Holstein)을 나타냅니다. 적어도 한 마리 이상의 Guernsey와 Holstein이 있음이 보장됩니다. 세 번째 줄에는 E1...EN이 주어집니다.

출력 형식: 가능한 리더 쌍의 수를 출력합니다.

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

int main(){
    int n;
    cin >> n;
    string breeds;
    cin >> breeds;
    vector<int> ranges(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> ranges[i];
    }
    
    int firstG = -1, lastG = -1, firstH = -1, lastH = -1;
    
    for(int i = 1; i <= n; ++i){
        if(breeds[i-1] == 'G'){
            if(firstG == -1) firstG = i;
            lastG = i;
        }
        else{
            if(firstH == -1) firstH = i;
            lastH = i;
        }
    }

    int countG = 0, countH = 0, pairs = 0;
    
    if(ranges[firstG] >= lastG) countG++;
    if(ranges[firstH] >= lastH) countH++;
    
    if(ranges[firstG] >= lastH && ranges[firstH] >= lastG){
        pairs++;
    }

    // 추가 조건 처리
    if(ranges[firstG] >= lastG){
        for(int i = 1; i < firstG; ++i){
            if(breeds[i-1] == 'H' && ranges[i] >= firstG){
                pairs++;
            }
        }
    }
    
    if(ranges[firstH] >= lastH){
        for(int i = 1; i < firstH; ++i){
            if(breeds[i-1] == 'G' && ranges[i] >= firstH){
                pairs++;
            }
        }
    }
    
    cout << (countG * countH + pairs) << endl;
}

문제 2: 공기 조화 II

농부 존의 소들이 가장 더운 여름을 보내고 있어, 그는 소들을 시원하게 유지하기 위해 에어컨을 설치하려 합니다. N 마리의 소들은 1에서 100까지 번호가 매겨진 연속적인 구역에 살고 있으며, 각 소는 특정 구역을 차지하고 있습니다. 서로 다른 소들은 겹치지 않는 구역에 있습니다. 각 소는 ci만큼의 온도 감소가 필요합니다. M개의 에어컨이 있으며, 각 에어컨은 ai부터 bi 구역을 식히며, pi만큼의 온도를 낮춥니다. 운영 비용은 mi입니다. 모든 소들의 요구사항을 충족시키면서 최소한의 비용으로 에어컨을 운영하세요.

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

int N, M;
vector<pair<int, pair<int, int>>> cows;
vector<tuple<int, int, int, int>> acs;

int cost[11]; // acs index
bool used[11];
int temp[101];

void dfs(int idx, int sum){
    bool done = true;
    for(auto &[s, t, c] : cows){
        bool ok = true;
        for(int i = s; i <= t; ++i){
            if(temp[i] < c){
                ok = false;
                break;
            }
        }
        if(!ok){
            done = false;
            break;
        }
    }
    
    if(done){
        cout << sum;
        exit(0);
    }
    
    if(idx == M) return;
    
    auto [a, b, p, m] = acs[idx];
    
    // Use AC
    for(int i = a; i <= b; ++i){
        temp[i] += p;
    }
    used[idx] = true;
    dfs(idx + 1, sum + m);
    
    // Do not use AC
    for(int i = a; i <= b; ++i){
        temp[i] -= p;
    }
    used[idx] = false;
    dfs(idx + 1, sum);
}

int main(){
    cin >> N >> M;
    cows.resize(N);
    for(int i = 0; i < N; ++i){
        cin >> cows[i].first >> cows[i].second.first >> cows[i].second.second;
    }
    acs.resize(M);
    for(int i = 0; i < M; ++i){
        cin >> get<0>(acs[i]) >> get<1>(acs[i]) >> get<2>(acs[i]) >> get<3>(acs[i]);
    }
    dfs(0, 0);
}

문제 3: Moo 작업

Bessie는 새로운 문자열 Q개를 받았습니다(1≤Q≤100). 각 문자열은 'M'과 'O'로만 이루어져 있으며, Bessie는 이를 "MOO"로 변환하려 합니다. 다음 작업을 사용할 수 있습니다:

• 첫 번째 또는 마지막 문자를 반대 문자로 변경('M'을 'O'로, 'O'를 'M'으로).
• 첫 번째 또는 마지막 문자를 삭제.

각 문자열을 "MOO"로 변환하는데 필요한 최소 작업 횟수를 출력하세요. 불가능하면 -1을 출력하세요.

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

int solve(const string &s){
    int min_ops = INT32_MAX;
    for(int i = 0; i + 2 < s.size(); ++i){
        string sub = s.substr(i, 3);
        int ops = 0;
        if(sub[0] != 'M') ops++;
        if(sub[1] != 'O') ops++;
        if(sub[2] != 'O') ops++;
        min_ops = min(min_ops, ops);
    }
    if(min_ops == INT32_MAX) return -1;
    return min_ops + (int)(s.size() - 3);
}

int main(){
    int Q;
    cin >> Q;
    while(Q--){
        string s;
        cin >> s;
        cout << solve(s) << "\n";
    }
}