A 문제

링크

연속된 두 개의 '달콤한' 요소가 있으면 나머지 요소들을 모두 먹을 수 없습니다.

코드 보기

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    string dishes[105];
    
    for (int i = 0; i < n; ++i) {
        cin >> dishes[i];
        if (i > 0 && dishes[i] == "달콤한" && dishes[i-1] == "달콤한") {
            cout << "불가능";
            return 0;
        }
    }
    
    cout << "가능";
    return 0;
}

B 문제

링크

격자 위에서 이동하는 로직을 구현합니다.

코드 보기

#include <iostream>

using namespace std;

int main() {
    int height, width, startX, startY;
    char grid[55][55];
    string moves;
    
    cin >> height >> width >> startX >> startY;
    for (int i = 0; i < height; ++i)
        for (int j = 0; j < width; ++j)
            cin >> grid[i][j];
            
    cin >> moves;
    for (char move : moves) {
        int newX = startX, newY = startY;
        switch(move) {
            case 'U': --newX; break;
            case 'D': ++newX; break;
            case 'L': --newY; break;
            case 'R': ++newY; break;
        }
        if (newX >= 0 && newX < height && newY >= 0 && newY < width && grid[newX][newY] == '.') {
            startX = newX;
            startY = newY;
        }
    }
    
    cout << startX << " " << startY;
    return 0;
}

C 문제

링크

각 맛별로 최소 몇 접시를 먹어야 하는지를 계산하고 그 중 가장 작은 값을 출력합니다.

코드 보기

#include <iostream>
#include <algorithm>

using namespace std;

bool compare(int a, int b) { return a > b; }

int main() {
    int totalDishes, sweetnessLimit, saltinessLimit;
    cin >> totalDishes >> sweetnessLimit >> saltinessLimit;
    int sweet[200005], salty[200005];
    
    for (int i = 0; i < totalDishes; ++i) cin >> sweet[i];
    for (int i = 0; i < totalDishes; ++i) cin >> salty[i];
    
    sort(sweet, sweet + totalDishes, compare);
    sort(salty, salty + totalDishes, compare);
    
    int minSweet = totalDishes, minSalty = totalDishes;
    long long currentSum = 0;
    for (int i = 0; i < totalDishes; ++i) {
        currentSum += sweet[i];
        if (currentSum > sweetnessLimit) {
            minSweet = i;
            break;
        }
    }
    currentSum = 0;
    for (int i = 0; i < totalDishes; ++i) {
        currentSum += salty[i];
        if (currentSum > saltinessLimit) {
            minSalty = i;
            break;
        }
    }
    
    cout << min(minSweet, minSalty);
    return 0;
}

D 문제

링크

이진 탐색을 사용하여 특정 범위 내의 요소 개수를 찾습니다.

코드 보기

#include <iostream>
#include <algorithm>

using namespace std;

long long findInRange(long long *arr, int size, long long lowerBound, long long upperBound) {
    int start = lower_bound(arr, arr + size, lowerBound) - arr;
    int end = upper_bound(arr, arr + size, upperBound) - arr;
    return end - start;
}

int main() {
    int numElements, queries;
    cin >> numElements >> queries;
    long long elements[100005];
    
    for (int i = 0; i < numElements; ++i) cin >> elements[i];
    sort(elements, elements + numElements);
    
    for (int q = 0; q < queries; ++q) {
        long long baseValue, range;
        cin >> baseValue >> range;
        long long low = 0, high = 1e16, mid;
        
        while (low < high) {
            mid = (low + high) / 2;
            if (findInRange(elements, numElements, baseValue - mid, baseValue + mid) < q + 1)
                low = mid + 1;
            else
                high = mid;
        }
        
        cout << high << endl;
    }
    
    return 0;
}

E 문제

링크

DP를 활용하여 각 단계에서의 최적해를 찾아갑니다.

코드 보기

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    int dishCount, maxSweetness, maxSaltiness;
    cin >> dishCount >> maxSweetness >> maxSaltiness;
    int sweetness[85], saltiness[85];
    int dp[85][20005][85];
    
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0] = 0;
    
    for (int i = 1; i <= dishCount; ++i) {
        cin >> sweetness[i] >> saltiness[i];
        for (int j = 0; j <= maxSweetness; ++j) {
            for (int k = 0; k < i; ++k) {
                dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k]);
                if (j + sweetness[i] <= maxSweetness && dp[i-1][j][k] + saltiness[i] <= maxSaltiness) {
                    dp[i][j + sweetness[i]][k+1] = min(dp[i][j + sweetness[i]][k+1], dp[i-1][j][k] + saltiness[i]);
                }
            }
        }
    }
    
    for (int k = dishCount; k >= 0; --k) {
        for (int j = 0; j <= maxSweetness; ++j) {
            if (dp[dishCount][j][k] <= maxSaltiness) {
                cout << min(dishCount, k + 1);
                return 0;
            }
        }
    }
    
    return 0;
}

F 문제

링크

Kruskal 알고리즘을 이용하여 최소 신장 트리를 구축합니다.

코드 보기

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

struct Edge {
    int from, to, cost;
};

bool compareEdges(Edge a, Edge b) {
    return a.cost < b.cost;
}

int main() {
    int nodeCount, queryCount;
    cin >> nodeCount >> queryCount;
    Edge edges[200005];
    set<int> unconnectedNodes;
    
    for (int i = 1; i < nodeCount; ++i) unconnectedNodes.insert(i);
    for (int i = 0; i < queryCount; ++i)
        cin >> edges[i].from >> edges[i].to >> edges[i].cost;
    
    sort(edges, edges + queryCount, compareEdges);
    long long totalCost = 0;
    
    for (int i = 0; i < queryCount; ++i) {
        int left = edges[i].from, right = edges[i].to;
        auto it = unconnectedNodes.lower_bound(left);
        while (it != unconnectedNodes.end() && *it + 1 <= right) {
            totalCost += edges[i].cost;
            it = unconnectedNodes.erase(it);
        }
    }
    
    if (unconnectedNodes.empty()) cout << totalCost;
    else cout << -1;
    
    return 0;
}