BOJ 30397 - 대구과학고등학교

 

문제 제목이 참... 좀 그렇다 ㅋㅋ

 

 

이 문제는 BOJ 1489와 같다. 

 

솔직히 이게 왜 플레지.. 생각이 들 정도로 단순한 그리디로 해결된다는 사실이다.

 

구해야 하는 것은 이안이와 예환이가 점수내기를 하고 이안이가 얻을 수 있는 최대 이익이다.

 

비교하기 쉽게 일단 정렬을 해보자. 이안이가 가장 최적의 효율로 내기에서 이기기 위해선 점수차가 최소가 되면서 이기거나 비기는 것이 중요하다. 여기까지 느낌을 잡았다면 그 후는 구현만 하면 된다. n제한은 10000으로 $O(n^2)$ 알고리즘을 사용할 수 있다. 이안이가 최소한의 점수차로 이길 수 있는 모든 과목 -> 무승부가 가능한 모든 과목 -> 지는 모든 과목순으로 점수를 계산해 주면 된다.

 

struct team {
	int point;
	bool used;
};
bool cmp(team a, team b) {
	return a.point > b.point;
}
bool cmp2(team a, team b) {
	return a.point < b.point;
}
int main() {
	fastio;
	int n;
	cin >> n;
	vector<team>a(n, { 0,false });
	vector<team>b(n, { 0,false });
	for (auto& v : a)cin >> v.point;
	for (auto& v : b)cin >> v.point;
	sort(all(a),cmp2);
	sort(all(b), cmp);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!b[j].used and a[i].point > b[j].point) {
				a[i].used = true; b[j].used = true;
				ans += 100;
				break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!a[i].used and !b[j].used and a[i].point == b[j].point) {
				a[i].used = true; b[j].used = true;
				ans += 20;
				break;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(!a[i].used and !b[j].used and a[i].point<b[j].point){
				a[i].used=true;b[j].used=true;
				ans-=50;
				break;
			}
		}
	}
	cout << ans;
	return 0;
}