A. 동일 숫자 페어 계산

배열 요소의 빈도를 저장하는 카운터를 활용하여 동일한 숫자 쌍의 최대 개수를 계산합니다. 각 숫자에 대해 발생 횟수를 2로 나눈 몫을 합산하여 해결합니다.

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int size;
        cin >> size;
        unordered_map<int, int> freqMap;
        long totalPairs = 0;
        
        for (int idx = 0; idx < size; idx++) {
            int num;
            cin >> num;
            freqMap[num]++;
        }
        
        for (auto& entry : freqMap) {
            totalPairs += entry.second / 2;
        }
        cout << totalPairs << '\n';
    }
    return 0;
}

B. 곱셈 쌍 탐색

주어진 정수 k에 대해 k-2의 약수 쌍 중 배열에 존재하는 조합을 찾습니다. k-2를 두 인수로 분해하고 두 인수가 모두 배열에 포함되는지 검증합니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int k;
        cin >> k;
        vector<int> arr(k);
        vector<bool> exists(k + 1, false);
        
        for (int idx = 0; idx < k; idx++) {
            cin >> arr[idx];
            if (arr[idx] <= k) exists[arr[idx]] = true;
        }
        
        int target = k - 2;
        bool found = false;
        
        for (int factor = 1; factor * factor <= target; factor++) {
            if (target % factor == 0) {
                if (factor <= k && target/factor <= k && exists[factor] && exists[target/factor]) {
                    cout << factor << ' ' << target/factor << '\n';
                    found = true;
                    break;
                }
            }
        }
        if (!found) cout << "-1\n";
    }
    return 0;
}

C. 합성수 인접 배열

인접한 요소의 합이 항상 합성수가 되도록 배열을 구성합니다. n ≤ 4인 경우 불가능하며, n ≥ 5인 경우 홀수와 짝수를 분리하여 특정 패턴으로 배치합니다.

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int n;
        cin >> n;
        
        if (n <= 4) {
            cout << "-1\n";
            continue;
        }
        
        for (int i = 7; i <= n; i += 2) cout << i << ' ';
        cout << "1 3 5 4 2 ";
        for (int i = 6; i <= n; i += 2) cout << i << ' ';
        cout << '\n';
    }
    return 0;
}

D. 장애물 점프 최적화

그리디 알고리즘과 최대 힙을 활용해 장애물을 넘기 위해 필요한 최소 부스터 수집 횟수를 계산합니다. 힙에서 가장 큰 부스터를 우선적으로 사용합니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int boosters, obstacles, initPower;
        cin >> boosters >> obstacles >> initPower;
        
        vector<pair<int, int>> barriers(obstacles);
        for (int i = 0; i < obstacles; i++) 
            cin >> barriers[i].first >> barriers[i].second;
        
        vector<pair<int, int>> powerUps(boosters);
        for (int i = 0; i < boosters; i++) 
            cin >> powerUps[i].first >> powerUps[i].second;
        
        sort(barriers.begin(), barriers.end());
        sort(powerUps.begin(), powerUps.end());
        
        priority_queue<int> maxHeap;
        int idx = 0, currentPower = initPower;
        int collectionCount = 0;
        bool feasible = true;
        
        for (auto& barrier : barriers) {
            int gap = barrier.second - barrier.first + 2;
            while (idx < boosters && powerUps[idx].first < barrier.first) {
                maxHeap.push(powerUps[idx].second);
                idx++;
            }
            while (!maxHeap.empty() && currentPower < gap) {
                currentPower += maxHeap.top();
                maxHeap.pop();
                collectionCount++;
            }
            if (currentPower < gap) {
                feasible = false;
                break;
            }
        }
        cout << (feasible ? collectionCount : -1) << '\n';
    }
    return 0;
}

E. 이진 문자열 복구

상호작용 문제로, 쿼리를 통해 이진 문자열을 복구합니다. 접두사에서의 0의 개수를 활용해 비트를 결정하며, 첫 번째 비트 집합 위치를 통해 초기 비트를 설정합니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int n;
        cin >> n;
        vector<int> prefixZeros(n + 1, 0);
        vector<int> result(n + 1, 0);
        
        for (int i = 2; i <= n; i++) {
            cout << "? 1 " << i << endl;
            cin >> prefixZeros[i];
        }
        
        if (prefixZeros[n] == 0) {
            cout << "! IMPOSSIBLE" << endl;
            continue;
        }
        
        bool initialized = false;
        for (int i = 2; i <= n; i++) {
            if (prefixZeros[i] > prefixZeros[i - 1]) {
                result[i] = 1;
            }
            if (!initialized && result[i] == 1) {
                int leadingOnes = (i - 1) - prefixZeros[i];
                for (int j = 1; j <= leadingOnes; j++) result[j] = 1;
                initialized = true;
            }
        }
        
        cout << "! ";
        for (int i = 1; i <= n; i++) cout << result[i];
        cout << endl;
    }
    return 0;
}

F. 공격 위치 최적화

이분 탐색으로 최소 공격 횟수를 결정합니다. 각 공격 횟수에 대해 적 처치 가능 여부를 확인하며, 좌표 압축과 구간 합을 활용해 위치 커버리지를 계산합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool validate(int attacks, int enemies, int range, vector<int>& health, vector<int>& pos) {
    vector<int> endpoints;
    for (int i = 0; i < enemies; i++) {
        int threshold = (health[i] + attacks - 1) / attacks;
        if (threshold > range) return false;
        int leftBound = pos[i] - (range - threshold);
        int rightBound = pos[i] + (range - threshold) + 1;
        endpoints.push_back(leftBound);
        endpoints.push_back(rightBound);
    }
    
    sort(endpoints.begin(), endpoints.end());
    endpoints.erase(unique(endpoints.begin(), endpoints.end()), endpoints.end());
    
    vector<int> diffArray(endpoints.size() + 1, 0);
    for (int i = 0; i < enemies; i++) {
        int threshold = (health[i] + attacks - 1) / attacks;
        int leftBound = pos[i] - (range - threshold);
        int rightBound = pos[i] + (range - threshold) + 1;
        int leftIdx = lower_bound(endpoints.begin(), endpoints.end(), leftBound) - endpoints.begin();
        int rightIdx = lower_bound(endpoints.begin(), endpoints.end(), rightBound) - endpoints.begin();
        diffArray[leftIdx]++;
        diffArray[rightIdx]--;
    }
    
    int coverage = 0;
    for (int i = 0; i < diffArray.size(); i++) {
        coverage += diffArray[i];
        if (coverage >= attacks) return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int enemies, range, attacks;
        cin >> enemies >> range >> attacks;
        vector<int> health(enemies), pos(enemies);
        for (int i = 0; i < enemies; i++) cin >> health[i];
        for (int i = 0; i < enemies; i++) cin >> pos[i];
        
        int low = 1, high = 1e9, result = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (validate(mid, enemies, range, health, pos)) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        cout << result << '\n';
    }
    return 0;
}

G. 소인수 경로 계수

동적 계획법과 포함-배제 원리를 적용해 경로 수를 계산합니다. 소인수 분해를 통해 공통 인자를 가진 이전 위치의 DP 값을 집계합니다.

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    vector<int> dp(n, 0);
    vector<vector<int>> primeFactors(1000001);
    vector<int> factorSum(1000001, 0);
    
    dp[0] = 1;
    for (int num : primeFactors[arr[0]]) {
        factorSum[num] = (factorSum[num] + dp[0]) % MOD;
    }
    
    for (int i = 1; i < n; i++) {
        int current = arr[i];
        vector<int> factors;
        int temp = current;
        for (int f = 2; f * f <= temp; f++) {
            if (temp % f == 0) {
                factors.push_back(f);
                while (temp % f == 0) temp /= f;
            }
        }
        if (temp > 1) factors.push_back(temp);
        
        vector<int> uniqueFactors = {1};
        for (int f : factors) {
            vector<int> newFactors;
            for (int uf : uniqueFactors) {
                newFactors.push_back(uf * f);
            }
            uniqueFactors.insert(uniqueFactors.end(), newFactors.begin(), newFactors.end());
        }
        
        for (int uf : uniqueFactors) {
            int sign = (__builtin_popcount(uf) % 2) ? 1 : -1;
            dp[i] = (dp[i] + sign * factorSum[uf] + MOD) % MOD;
        }
        
        for (int uf : uniqueFactors) {
            factorSum[uf] = (factorSum[uf] + dp[i]) % MOD;
        }
    }
    cout << dp[n - 1] << '\n';
    return 0;
}