백준 10899번 King of penalty

문제 링크입니다: https://www.acmicpc.net/problem/10899

10899번: King of penalty

그리디하게 접근하면 되는 문제였습니다.

패널티가 가장 크게 잡히기 위해서는 정확히 (P - 1)분에 마지막 문제를 제출해야합니다.

또한, 처음 푸는 문제가 소요되는 시간이 제일 길어야하고 마지막 푸는 문제에 소요되는 시간이 제일 짧아야한다는 것도 알 수 있습니다.

최대한 많은 문제를 풀면서 가장 많은 페널티를 얻는 것이 목표이기 때문에

우리는 (P - 1)분부터 역으로 문제 풀이에 소요되는 시간이 작은 순부터 빼가면서 더해나가면 됩니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	typedef struct
	{
	long long duration;
	int cnt;
	} Result;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int P, N;
	cin >> P >> N;
	vector<int> durations(N);
	for (int i = 0; i < N; i++)
	{
	cin >> durations[i];
	}
	sort(durations.begin(), durations.end());
	int sum = 0;
	int timeLimit = P - 1;
	Result result = { 0, 0 };
	for (int i = 0; i < N && timeLimit >= durations[i]; i++)
	{
	result.duration += timeLimit;
	timeLimit -= durations[i];
	result.cnt++;
	}
	cout << result.cnt << " " << result.duration << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~