백준 BOJ 3758 - KCPC

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

3758번: KCPC

정렬 문제.

1. 점수가 높은 팀
2. 문제 제출 횟수가 적은 팀
3. 마지막 제출 시간이 더 빠른 팀

 

순서대로 정렬해주면 되는 문제.

이것저것 관리하기 귀찮으므로 구조체를 사용했다.

N이 별로 크지 않으므로 직접 비교해서 N^2 정렬을 해줘도 좋다만

sort 함수의 정렬순서를 바꾸는 비교함수를 직접 작성해보는 연습용 문제로써

나쁘지 않은듯.

 

struct solve{
	int cnt = 0;
	int time = 0;
	int sc = 0;
	int idx = 0;
};

bool cmp(const solve &a, const solve &b){
	if(a.sc != b.sc) return a.sc > b.sc;
	if(a.cnt != b.cnt) return a.cnt < b.cnt;
	return a.time < b.time;
}

점수를 저장할때

입력으로 들어오는 수를 전부 더하는게 아니라

문제번호를 보고 해당 문제번호에서 얻어낸 최대 점수를

따로 배열 등에 저장해주어야 한다.

 

이 최대 점수들끼리 더해서

최종적으로 정렬할 배열에 저장해주면 된다.

 

나중에 출력에 써먹기 위해서 구조체 solve에

팀 번호 idx 변수를 추가해주는것이 편하다.

 

#include <bits/stdc++.h>
using namespace std;

struct solve{
	int cnt = 0;
	int time = 0;
	int sc = 0;
	int idx = 0;
};

bool cmp(const solve &a, const solve &b){
	if(a.sc != b.sc) return a.sc > b.sc;
	if(a.cnt != b.cnt) return a.cnt < b.cnt;
	return a.time < b.time;
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int T;
	cin >> T;
	while(T--){
		int n,k,t,m;
		int a,b,c;
		cin >> n >> k >> t >> m;
		
		vector<solve> v(n+1);
		int arr[123][123] = {0};
		
		for(int i=0; i<m; i++){
			cin >> a >> b >> c;
			arr[a][b] = max(arr[a][b], c);
			v[a].cnt++;
			v[a].time = max(v[a].time, i);
			v[a].idx = a;
		}
		
		for(int i=1; i<=n; i++){
			for(int j=1; j<=k; j++){
				v[i].sc += arr[i][j];
			}
		}
		
		sort(v.begin()+1, v.end(), cmp);
		
		for(int i=1; i<=n; i++){
			if(v[i].idx == t){
				cout << i << "\n";
				break;
			}
		}
	}
	return 0;
}