C++ 백준 25391번: 특별상

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

25391번: 특별상

 

 

풀이

처음에 예제에 있는 설명을 보고

주최자가 준 점수가 높지만 심판이 준 점수가 낮아서 특별상으로 뽑는다 -> 하지만 첫 번째 학생이 그렇지 않음

주최자가 준 점수 - 심판이 준 점수를 계산해서 할려고 했지만 실패

도저히 아이디어가 안 떠올라서 질문게시판에 반례를 봤는데

 

nadoo1313님 댓글

이걸 보고 깨달았다. 무조건 본상을 수여한 학생은 심판 점수가 높으니, 본상을 수여하는 사람 수만큼 뽑고, 그 후 본상을 수여 못 한 사람들 중에 주최자 점수가 높은 사람을 뽑으면 된다.

구현은 심판 점수로 내림차순 정렬해서 K명을 먼저 뽑고, 주최자 점수로 내림차순 정렬해서 본상을 받지 못한 사람들 중 높은 점수로 M명 뽑았다. 벡터와 pair를 사용했고 sort의 compare 함수는 봐도 어떻게 작동하지는 잘 모르겠어서 한 번 정리해야겠다는 생각이 들었다,,,

---

#include <bits/stdc++.h>
using namespace std;
vector <pair<long, long>> score; // fir :  심판, sec = 주최자
bool compare(const pair<long, long>& a, const pair<long, long>& b)
{
	return a.second > b.second;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int  num, m, n;
	cin >> num >> m>> n;
	while (num--) {
		long a, b;
		cin >> a >> b;
		score.push_back(make_pair(b, a));

	}
	sort(score.begin(), score.end(),greater<>()); // 심판 내림차순


	long sum = 0; 
	for (long i = 0; i < n; i++) { //심판은 무조건 뽑음.
		sum += score[i].second;
		score[i].first = -100; // 심판이 뽑은 사람은 뽑지 않기 위해 -100 값 적용
	}
	sort(score.begin(), score.end(), compare); // 주최자 내림차순 

	int cnt = 0;
	int i = 0;
	while (true) {
		if (cnt == m) {
			break;
		}
		if (score[i].first != -100) {
			// 심판이 뽑지 않은 사람 중에 주최자가 높은 점수를 준 사람 뽑기
			sum += score[i].second;
			cnt++;
		}
		i++;

	}
	cout << sum << '\n';

	return 0;
} //main

---

아 그리고 드디어 골드5 달성!

문제 양치기해서 아직 실력은 실버4-5인건 안 비밀

이제 코테 준비도 할겸 dfs, bfs, dp, 브루트포스, 그리디 등 주로 나오는 알고리즘 위주로 풀어야겠다...!