03.03. And the Winner Is... Ourselves![Greedy Algorithm][백준 17509]

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

17509번: And the Winner Is... Ourselves!

 

Algorithm classification : Greedy Algorithm, Sorting

 

03.03.1. Problem

Let us remind you about how the total penalties are calculated for this contest:

• When you solve a problem at T minutes, T+20V is added to your penalty, where V$V$ is the number of incorrect verdicts (except compile errors) received on that problem.
• If you do not solve a problem before the contest ends, the incorrect verdicts on that problem are not counted as penalties.

Here is a bad news for all of you: we, the problem setters, are planning to join the competition and solve our own problems!

We know our problems really well, so we can solve all the problems before the contest ends. Furthermore, we can precisely predict how long it takes to solve each problem, and how many incorrect verdicts (except compile errors) we get in each problem. Depending on the order of the problems we solve, our total penalty might differ. What is the minimum penalty if we solve all problems?

 

03.03.2. Input limit

11 lines are given as the input. The i-th line contains two space-separated integers, D_i and V_i, where D_i is the amount of minutes required to solve the i-th problem, and Vi$V_i$ is the number of incorrect verdicts on the i-th problem.

For each i, 1≤D_i and 0≤V_i≤1 000. Also, ∑i from 1 to 11 : D_i ≤ 300.

 

03.03.3. Output

Output the minimum penalty if we solve all problems.

 

03.03.4. Solution

시간과 틀린 횟수 중 무엇이 중요한 인자인지 고민해 보시면 될 듯 합니다. 만약 vector를 사용하실 줄 모르신다면 이렇게 배열로 구현하셔도 됩니다. 하지만 많이 귀찮죠. 

	for(i = 0; i < 11; i++){
		scanf("%d %d", &data[i][0], &data[i][1]);
	}
	for(i = 0; i < 11; i++){
		for(j = i; j < 11; j++){
			if(data[i][0] < data[j][0]){
				temp = data[i][0];
				data[i][0] = data[j][0];
				data[j][0] = temp;
				
				temp = data[i][1];
				data[i][1] = data[j][1];
				data[j][1] = temp;
			}
		}
	}
	
	int t = 0;
	for(i = 10; i >= 0; i--){
		//printf("%d %d\n", data[i][0], data[i][1]);
		t += data[i][0];
		
		ans += t + 20 * data[i][1];
	}
	printf("%d", ans);

만약 vector 라이브러리를 사용한다면 조금 더 깔끔해 집니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define n 11

using namespace std;

int main() {
    vector<pair<int, int>> problems(n);

    for(int i = 0; i < n; i++) {
        cin >> problems[i].first >> problems[i].second;
    }

    sort(problems.begin(), problems.end());

    int penalty = 0;
    int time = 0;
    for(int i = 0; i < n; i++) {
        time += problems[i].first;
        penalty += (time + 20 * problems[i].second);
    }
    
    cout << penalty;

    return 0;
}