백준 1900. 레슬러

레슬러

그리디, 정렬 문제

1. 간단 설명

---

번역본 문제라 굉장히 혓바닥이 길다

즉 요약하면

1. 레슬링 선수 A의 경기력은 ‘A의 힘’ + ‘B의 힘’ * ‘A가 착용하고 있는 마술 링의 힘’ 으로, 링의 마술력과 상대에 의존한다
2. 경기력이 높은 선수가 경기에서 이긴다
3. 축제 기간에 각 레슬링 선수는 다른 모든 선수들과 한번씩 경기를 가진다
4. 선수들은 그가 이긴 경기 수 + 선수들의 줄에서 자기보다 앞에 있는데 자기가 이긴 선수의 수애 따라 금화를 보상받는다
5. 수여하는 금화가 최소가 되도록 할 때, 그 줄의 순서를 출력

2. 예시

---

A의 힘 10, 마술링 3
B의 힘 18, 마술링 4
C의 힘 15, 마술링 5

A vs B (A승)
A의 경기력 = 10 + 3 * 18 = 64
B의 경기력 = 18 + 4 * 10 = 58

A vs C (C승)
A의 경기력 = 10 + 3 * 15 = 55
C의 경기력 = 15 + 5 * 10 = 65 

B vs C (C승)
B의 경기력 = 18 + 4 * 15 = 78
C의 경기력 = 15 + 5 * 18 = 105

A, B, C 순서대로 금화를 주면,

A는 1승, 맨앞이므로 금화 한개

B는 두번째지만, 0승이므로 0개

C는 세번째 서있었고, 2승이므로 2+2개, 4개를 받으므로

총 금화는 5개가 지출된다

최소 금화를 지출하는 방법은 C, A, B 순서로 총 금화 4개면 된다

3. 알고리즘

---

어짜피 이길 수 있는 상대는 정해져있다

선수 i의 경기력은 i 경기력 = i의 힘 + (i의 마술링 * 상대 j의 힘) 으로 계산된다

그러므로, 선수 i에 대한 모든 상대 선수들과의 경기 결과를 체크해본다

선수 i가 몇번 이기는지 기록해 두고,

이 데이터를 확인해서 가장 많이 이기는 선수를 앞쪽에 배치할수록 금화를 적게 쓸 수 있다

1. N과, 선수 정보 입력받기
2. 1번 선수부터 N번까지 해당 선수가 몇승할 수 있는지 계산
	2-1. 자기 자신을 제외한 선수들과 경기력 비교
	2-2. 만약 자신의 경기력이 더 높다면, 승수 + 1
3. 승수를 내림차순으로 정렬
4. 출력

4. 소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
struct Player {
	int num;
	int power;
	int ring;
	int win_cnt = 0;
};
vector<Player> v;

struct cmp {
	bool operator()(const Player& A, const Player& B) {
		// 1. 승수 내림차순 정렬
		if (A.win_cnt != B.win_cnt) {
			return A.win_cnt > B.win_cnt;
		}
		// 2. 링 파워 내림차순
		if (A.ring != B.ring) {
			return A.ring > B.ring;
		}
		// 3. 파워 내림차순
		if (A.power != B.power){
			return A.power > B.power;
		}
		// 4. 등록순서
		return A.num < B.num;
	}
};

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N;
	v.resize(N);

	for (int i = 0; i < N; i++) {
		int tmp_pow, tmp_ring;
		cin >> tmp_pow >> tmp_ring;
		v[i] = { i, tmp_pow, tmp_ring, 0 };
	}
}

void Calc_WinRate(int player) {
	for (int i = 0; i < N; i++) {
		if (i == player) continue; // 자기자신은 패스
		int player_stat = v[player].power + v[player].ring * v[i].power;
		int oppo_stat = v[i].power + v[i].ring * v[player].power;

		if (player_stat > oppo_stat) {
			v[player].win_cnt++;
		}
	}
}

int main() {
	Input();

	for (int i = 0; i < N; i++) {
		Calc_WinRate(i);
	}
	
	sort(v.begin(), v.end(), cmp());

	for (int i = 0; i < N; i++) {
		cout << v[i].num + 1 << '\n';
	}

	//for (int i = 0; i < N; i++) {
	//	cout << player[]
	//	printf("Player[%d] : %d, %d, %d \n", v[i].num, v[i].power, v[i].ring, v[i].win_cnt);
	//}

	return 0;
}

처음에 뇌정지 왔는데 문제를 잘 읽어보고

조금 생각해보니 정렬 문제인것 같아서 쉽게 풀 수 있었다