1787C - Remove the Bracket

동적 계획법(DP)을 사용하여 괄호를 제거했을 때의 최소 비용을 계산하는 문제입니다. 각 원소를 특정 임계값 $k$를 기준으로 두 부분으로 나누고, 이전 상태의 최소값을 갱신하는 방식으로 접근합니다. 상태 전이 시 곱셈 연산이 발생하므로, 각 위치에서 0번과 1번 선택지에 따른 누적 비용을 독립적으로 관리하여 최적해를 도출합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

void processTestCase() {
    int seqLen, limit;
    cin >> seqLen >> limit;
    vector<ll> seq(seqLen + 1);
    for (int i = 1; i <= seqLen; ++i) cin >> seq[i];

    vector<vector<ll>> parts(seqLen + 1, vector<ll>(2));
    parts[1][0] = parts[1][1] = seq[1];
    parts[seqLen][0] = parts[seqLen][1] = seq[seqLen];

    for (int i = 2; i < seqLen; ++i) {
        if (seq[i] >= limit) {
            parts[i][0] = limit;
            parts[i][1] = seq[i] - limit;
        } else {
            parts[i][0] = 0;
            parts[i][1] = seq[i];
        }
    }

    vector<vector<ll>> minCost(seqLen + 1, vector<ll>(2, 0));
    for (int i = 2; i <= seqLen; ++i) {
        ll cost00 = minCost[i-1][0] + parts[i-1][1] * parts[i][0];
        ll cost10 = minCost[i-1][1] + parts[i-1][0] * parts[i][0];
        minCost[i][0] = min(cost00, cost10);

        ll cost01 = minCost[i-1][0] + parts[i-1][1] * parts[i][1];
        ll cost11 = minCost[i-1][1] + parts[i-1][0] * parts[i][1];
        minCost[i][1] = min(cost01, cost11);
    }

    cout << min(minCost[seqLen][0], minCost[seqLen][1]) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tests;
    cin >> tests;
    while (tests--) processTestCase();
    return 0;
}

1393C - Pinkie Pie Eats Patty-cakes

동일한 원소 사이의 최소 거리를 최대화하는 문제입니다. 가장 많이 등장하는 원소의 빈도수를 기준으로 수학적 공식을 도출하여 $O(N)$ 시간에 해결할 수 있습니다. 최대 빈도수를 가진 원소들의 개수를 파악하고, 나머지 원소들을 이들 사이에 최대한 균등하게 배치하는 그리디한 관점에서 수식을 유도합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> freq(n + 1, 0);
    int maxFreq = 0;

    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        freq[val]++;
        maxFreq = max(maxFreq, freq[val]);
    }

    int maxFreqCount = 0;
    for (int i = 1; i <= n; ++i) {
        if (freq[i] == maxFreq) maxFreqCount++;
    }

    int result = (n - maxFreqCount * maxFreq) / (maxFreq - 1) + maxFreqCount - 1;
    cout << result << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

1334C - Circle of Monsters

원형으로 배열된 몬스터를 처치할 때 필요한 최소 공격 횟수를 구하는 문제입니다. 인접한 몬스터의 폭발 데미지를 고려하여 실제 필요한 공격량을 조정한 후, 누적 합(Prefix Sum)을 활용해 모든 시작점에 대한 비용을 효율적으로 계산합니다. 배열을 두 배로 확장하여 원형 구조를 선형으로 풀어내는 기법을 사용합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<ll> health(2 * n + 1), blast(2 * n + 1);
    
    for (int i = 1; i <= n; ++i) {
        cin >> health[i] >> blast[i];
        health[i + n] = health[i];
    }
    
    for (int i = 1; i <= n; ++i) {
        blast[i] = min(blast[i], health[i + 1]);
        blast[i + n] = blast[i];
    }

    vector<ll> prefH(2 * n + 1, 0), prefB(2 * n + 1, 0);
    for (int i = 1; i <= 2 * n; ++i) {
        prefH[i] = prefH[i - 1] + health[i];
        prefB[i] = prefB[i - 1] + blast[i];
    }

    ll minShots = 2e18;
    for (int i = 1; i <= n; ++i) {
        ll totalH = prefH[i + n - 1] - prefH[i - 1];
        ll totalB = prefB[i + n - 2] - prefB[i - 1];
        minShots = min(minShots, totalH - totalB);
    }
    
    cout << minShots << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

1411C - Peaceful Rooks

체스판 위의 룩(Rook)을 대각선으로 이동시키는 최소 이동 횟수를 구하는 문제입니다. 좌표를 그래프의 간선으로 모델링하고, 서로소 집합(Disjoint Set Union)을 사용하여 사이클 존재 여부를 판별합니다. 사이클이 형성된 경우 추가 이동이 필요하다는 점을 활용하여 그래프 이론과 자료구조를 결합한 최적화를 수행합니다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;

int findRoot(int node) {
    if (node == parent[node]) return node;
    return parent[node] = findRoot(parent[node]);
}

void solve() {
    int n, m;
    cin >> n >> m;
    parent.resize(n + 1);
    for (int i = 1; i <= n; ++i) parent[i] = i;

    int moves = 0;
    for (int i = 0; i < m; ++i) {
        int r, c;
        cin >> r >> c;
        if (r == c) continue;
        
        moves++;
        int rootR = findRoot(r);
        int rootC = findRoot(c);
        
        if (rootR == rootC) {
            moves++;
        } else {
            parent[rootR] = rootC;
        }
    }
    cout << moves << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}