[BOJ-2461] 대표 선수(C++)

백준 2461 대표 선수

 

[BOJ-21925 ] 짝수 팰린드롬(C++)

 

문제 설명

 

 - N개의 학급이 존재하고, 각 학급의 학생 수는 모두 M명이다.

 

 - 학생들은 저마다 능력을 나타내는 능력치를 가지고 있고, 능력치는 학생마다 서로 다르다.

 

 - 한 반에서 한 명의 대표 선수를 선발한다.

 

 - 각 반 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려 한다.

 

 - 대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 출력하라.

 

---

 

입력 값

 

 - 첫 번째 줄에는 학급의 수를 나타내는 N과 학생의 수 M이 빈칸을 사이에 두고 주어진다.

   ( 1 <= N, M <= 1,000 )

 

 - 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학급 학생들의 능력치를 나타내는 M개의 양의 정수가 하나의 빈칸을 사이에 두고 주어진다.

   

 - 능력치는 0이상 10억 이하이다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 각 반에서 한 명의 학생들을 뽑고, 그 학생들의 최대 - 최소 능력치의 최소 값을 찾는 문제이다.

 

 - 단순하게 생각하면, N개의 반이 존재하고, 해당 반에 M명이 존재한다.

   즉, 한 반에서 대표를 뽑는 경우의 수는 MC1 = M이고, 반이 N개이기 때문에 $M^N$의 경우의 수를 살펴보면 된다.

 

 - $M^N$의 경우 최대 $1000^1000$이기 때문에 당연히 불가능하다.

 

 - 하지만, 이 문제를 잘 살펴보면 좀 더 간단하게 답을 구할 수 있다.

 

 - 이 문제는 결국 각 반 대표들 간 최대 - 최소 값을 구해야 하는 문제이다.

 

 - 각 반 대표의 능력치가 10, 20, 30, 40, 100인 경우 100-10 = 90이 된다.

   10, 11, 12, 13, 100의 경우에도 90이고, 10, 95, 96, 97, 100 인 경우에도 90이다.

 

 - 결론적으로 최대 or 최소 값만 변화시키면 된다는 것이다.

 

 - 문제 해결 과정은 다음과 같다.

   1. 각 반을 능력치 순으로 내림차순 정렬한다.

   2. 각 반의 처음 값(가장 큰 값)을 하나씩 뽑는다.

   3. 그 값들 중 가장 큰 값과 작은 값을 비교하여 저장한다.

   4. 가장 큰 값은 제거하고, 그 반에서 해당 값의 다음 인덱스 값을 다시 찾는다.

   5. 하나의 반의 모든 사람을 탐색했다면 종료하고, 아니면 3번으로 돌아가서 비교한다.

 

 - 이 문제의 경우 시간복잡도는

  모든 반의 학생들을 능력치 순으로 정렬하기 위해 Nx(MlogM),

  모든 반의 사람을 탐색하는 경우 NxM의 시간이 걸리고,

  해당 경우에 가장 큰 값을 가져와야 하기 때문에 logN의 시간이 걸린다.

  즉, O(2NMlogN) 이고, 최대 2x1000x1000xlog(1000)  = 약 2000만의 시간이 걸린다.

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

vector<int> v[1001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, p;

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> p;
			v[i].push_back(p);
		}
	}
	int result = INT_MAX;

	int minNum = INT_MAX;
	// 값, 반 번호, 학생 번호
	priority_queue<pair<int, pair<int,int>>> pq;

	for (int i = 0; i < N; i++) {
		sort(v[i].begin(), v[i].end(),greater<int>());
		minNum = min(minNum, v[i][0]);
		pq.push({ v[i][0],{i,0} });
	}
	
	while (pq.size()>0) {
		int maxNum = pq.top().first;
		int maxIndex = pq.top().second.first;
		int maxArrIndex = pq.top().second.second;

		pq.pop();

		result = min(result, maxNum - minNum);

		if (maxArrIndex + 1 == M) {
			break;
		}
		minNum = min(minNum, v[maxIndex][maxArrIndex + 1]);
		pq.push({ v[maxIndex][maxArrIndex + 1] ,{maxIndex,maxArrIndex + 1} });
		

		
	}

	cout << result << endl;;


	

	return 0;
}