[백준] 2461번 대표 선수 (C++)

https://www.acmicpc.net/problem/2461

 

 

이 문제는 N(학급)과 M(각 학급의 개수)가 주어지며 행렬 형태로 각 학생들의 능력치가 주어진다. 이때 각 학급에서 한명씩 선택했을때 최대 능력치와 최소 능력치의 차이를 최소로 만들어야 한다.

 

 

단순히 완전탐색을 할 경우 O(N^M)으로 N이 최대 1000이므로 굉장히 큰 숫자가 나올 것이다 따라서 이를 최적화 하기 위해 능력치를 오름차순 or 내림차순으로 정렬해야겠다고 생각하였고

 

필자는 오름차순으로 정렬했기에 숫자가 커지므로 최소힙이 있어야겠다고 생각을 하였다.

 

로직 자체는 어렵지 않으며 각 학급의 0번째 학생을 최소힙에 넣어주며 힙에서 하나씩 빼주며 해당 학급의 다음으로 높은 능력치의 학생을 넣어주며 최댓값도 갱신해주었다. 결국 필요한건 최대와 최소기 때문에 중간에 있는것은 상관이 없다. 따라서 각 학급 얘들의 최소를 하나씩 빼고 넣어주며 최소 차이를 갱신해주었다.

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M;
int graph[1001][1001];
int arr[1001];
priority_queue<pii, vector<pii>, greater<pii>> pq;

void Print() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

void solve() {
    for(int i = 0; i < N; i++) {
        sort(graph[i], graph[i]+M);
    }

    int max_val = 0;

    for(int i = 0; i < N; i++) {
        pq.push({graph[i][0], i});
        max_val = max(max_val, graph[i][0]);
    }

    int answer = max_val - pq.top().first;

    while(true) {
        int val = pq.top().first;
        int idx = pq.top().second;
        pq.pop();

        answer = min(answer, max_val - val);

        if(++arr[idx] < M) {
            pq.push({graph[idx][arr[idx]], idx});
            max_val = max(max_val, graph[idx][arr[idx]]);
        }
        else {
            break;
        }
    }

    cout << answer;
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> graph[i][j];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}