[BOJ 17509 // C++] And the Winner Is... Ourselves!

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17509번 문제인 And the Winner Is... Ourselves!이다.

문제는 아래 링크를 확인하자.

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

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

문제의 틀린 횟수에 따른 페널티는 문제를 어떤 순서로 풀더라도 20 * (문제를 틀린 횟수)만큼 받게 된다.

 

문제를 푼 시간에 따른 페널티를 최소화하는 방법은 풀이에 소요되는 시간이 짧은 문제서부터 빠르게 푸는 것이다. 어떤 풀이시간이 오래걸리는 문제를 조금 걸리는 문제보다 빨리 풀었을 경우, 둘의 순서를 바꾸는 것만으로 시간에 따른 페널티가 감소한다는 것을 관찰한다면 위의 방식이 최적의 방법이라는 것을 쉽게 증명해낼 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using namespace std;

int arr[11];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int ans = 0, t = 0;

	for (int i = 0; i < 11; i++) {
		cin >> arr[i];
		int x; cin >> x;
		ans += x * 20;
	}

	sort(arr, arr + 11);
	for (int i = 0; i < 11; i++) {
		t += arr[i];
		ans += t;
	}

	cout << ans;
}