[백준 / 17509] And the Winner Is... Ourselves! - C++

www.acmicpc.net/problem/17509

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

문제 : 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 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?

 

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

For each i, 1≤Di and 0≤Vi≤1 000. Also, ∑i=111Di≤300.

 

출력 : Output the minimum penalty if we solve all problems.

 

문제를 대충 해석해 보면 문제를 풀 때마다 문제를 솔브한 시간 + 20*틀린 횟수가 페널티 점수로 더해진다.

모든 문제를 풀었을 때 가장 작은 페널티 점수를 출력하면 된다.

 

문제를 솔브한 시간 페널티와 틀린 횟수 페널티는 서로 영향을 주지 않기 때문에 따로따로 점수를 더해주면 된다.

따라서 시간 페널티를 적게 받는것이 중요한데, 시간 페널티를 적게 받으려면 푸는데 시간이 별로 안 걸리는 문제부터 풀어야 한다.

 

예를 들어 푸는데 걸리는 시간이 20 10 30이라 생각하여 보자,

• 10 20 30 순서대로 풀면 페널티는 10 + (10 + 20) + (10 + 20 + 30) = 100이다.
• 30 20 10 순서대로 풀면 페널티는 30 + (20 + 30) + (10 + 20 + 30) = 140이다.

따라서 문제를 푸는데 걸리는 시간을 오름차순으로 정렬해준 뒤 작은것부터 페널티를 계산하고,

틀린 횟수 페널티는 따로 세어 서로 더해주면 된다.

 

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
pair <int, int> arr[12];
int main(){
	int pen = 0;
	int cnt = 0;
	for(int i =0;i<11;i++){
		scanf("%d %d",&arr[i].first,&arr[i].second);	
	}
	sort(arr,arr+11);
	for(int i =0;i<11;i++){
		pen += cnt + arr[i].first;
		cnt += arr[i].first;
	}
	for(int i =0;i<11;i++){
		pen += (20 * arr[i].second);
	}
	printf("%d",pen);
}

 

사실 문제가 영어로 되어있길래 외국 대회 문제인줄 알았는데 카이스트 대회였다;;