문제 설명

n명의 참가자가 각각 능력치와 열정도를 가지고 있을 때, 팀 내 최대와 최소 능력치 차이가 주어진 X 이하인 조건에서 팀 전체 열정도의 합을 최대화하는 문제입니다.

입력 형식

첫 줄: 참가자 수 n
다음 n줄: 각 참가자의 능력치와 열정도
마지막 줄: 허용 가능한 최대 능력치 차이 X

출력 형식

조건을 만족하는 최대 열정도 합 출력

데이터 범위

• 30% 테스트 케이스: 1 ≤ n ≤ 100
• 60% 테스트 케이스: 1 ≤ n ≤ 10⁴
• 100% 테스트 케이스: 1 ≤ n ≤ 10⁵, 1 ≤ X ≤ 10⁹, 능력치와 열정도는 1~10⁹

예제

입력:
5
10 21
20 34
30 27
40 89
50 54
20

출력:
170

해결 방법 1: 완전 탐색(DFS)

모든 가능한 조합을 탐색하는 방법으로, n이 작을 때만 사용 가능합니다. 시간 복잡도는 O(n!)입니다.

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

struct Participant {
    int ability;
    int passion;
};

Participant arr[100];
long maxPassion;
int diffLimit, n;

void explore(int idx, long currentSum, int minAbil, int maxAbil) {
    if(idx == n) {
        if(currentSum > maxPassion) maxPassion = currentSum;
        return;
    }
    for(int next = idx; next < n; next++) {
        int newMin = min(minAbil, arr[next].ability);
        int newMax = max(maxAbil, arr[next].ability);
        if(newMax - newMin > diffLimit) continue;
        explore(next + 1, currentSum + arr[next].passion, newMin, newMax);
    }
    if(currentSum > maxPassion) maxPassion = currentSum;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i].ability >> arr[i].passion;
    cin >> diffLimit;
    explore(0, 0, 1e9+1, 0);
    cout << maxPassion;
    return 0;
}

해결 방법 2: 정렬 및 이중 루프

능력치 기준으로 정렬 후 각 시작점에서 가능한 최대 지점까지 열정도를 누적합니다. 시간 복잡도 O(n²)로 중간 규모 데이터까지 처리 가능합니다.

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

struct Member {
    int capability;
    int enthusiasm;
};

bool compare(Member m1, Member m2) {
    return m1.capability < m2.capability;
}

int main() {
    int n, maxDiff;
    cin >> n;
    Member team[100000];
    for(int i = 0; i < n; i++)
        cin >> team[i].capability >> team[i].enthusiasm;
    cin >> maxDiff;
    
    sort(team, team + n, compare);
    
    long maxTotal = 0;
    for(int start = 0; start < n; start++) {
        long current = 0;
        for(int end = start; end < n; end++) {
            if(team[end].capability - team[start].capability > maxDiff) break;
            current += team[end].enthusiasm;
        }
        maxTotal = max(maxTotal, current);
    }
    cout << maxTotal;
    return 0;
}

해결 방법 3: 슬라이딩 윈도우

정렬 후 두 포인터 기법으로 효율적으로 구간을 관리하며 최적해를 찾습니다. 시간 복잡도 O(n log n)으로 대규모 데이터 처리에 적합합니다.

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

struct Competitor {
    int skill;
    int zeal;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int playerCount, maxGap;
    cin >> playerCount;
    vector<Competitor> players(playerCount);
    for(int i = 0; i < playerCount; i++)
        cin >> players[i].skill >> players[i].zeal;
    cin >> maxGap;
    
    sort(players.begin(), players.end(), [](const Competitor& a, const Competitor& b) {
        return a.skill < b.skill;
    });
    
    long windowSum = 0, maxZealSum = 0;
    int left = 0;
    
    for(int right = 0; right < playerCount; right++) {
        windowSum += players[right].zeal;
        while(players[right].skill - players[left].skill > maxGap) {
            windowSum -= players[left].zeal;
            left++;
        }
        maxZealSum = max(maxZealSum, windowSum);
    }
    cout << maxZealSum;
    return 0;
}