과제

www.acmicpc.net/problem/13904

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	6570	3363	2681	51.627%

문제

웅찬이는 과제가 많다.
하루에 한 과제를 끝낼 수 있는데, 과제마다 마감 일이 있으므로 모든 과제를 끝내지 못할 수도 있다.
과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.
가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다.
웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.
다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다.
d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

예제 출력 1

185

힌트

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고,
세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

출처

University > 서강대학교 > 제12회 총장배 서강대학교 프로그래밍 대회 Champion E번

University > 서강대학교 > 제12회 총장배 서강대학교 프로그래밍 대회 Master E번

• 문제를 만든 사람: Telcontar

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

예제 입력 A

6
5 3
5 3
5 3
4 2
4 1
4 2

예제 출력 A

13

예제 입력 B

4
9 9
9 9
9 9
1 10

예제 출력 B

37

예제 입력 C

3
1 1
1 2
1 3

예제 출력 C

3

예제 입력 D

4
5 100
2 2
2 2
2 2

예제 출력 D

104

입력 확인 코드

일단 과제들을 점수가 높은 순으로 정리한다.

#include <iostream>
#include <queue>
#include <map>

using namespace std;

multimap<int, int, greater<int>> myMultimap;
multimap<int, int, greater<int>> ::iterator iter;

int temp, temp2 ,N = 0;

void Initailization()
{
	cin >> N;
	while (N > 0)
	{
		cin >> temp >> temp2;
		myMultimap.insert(make_pair(temp2, temp));
		N--;
	}
}

int main()
{
	Initailization();
	
	for (iter = myMultimap.begin(); iter != myMultimap.end();iter++)
	{
		cout << "점수 : " << iter->first << "  남은 일수 : " << iter->second << " \n";
	}

	return 0;
}

잘못된 로직과 코드

#include <iostream>
#include <map>

using namespace std;

multimap<int, int, greater<int>> myMultimap;
multimap<int, int, greater<int>> ::iterator iter;

int temp, temp2 ,N = 0;
int curDay = 1;
int maxDay = 0;
int result = 0;

void Initailization()
{
	cin >> N;
	while (N > 0)
	{
		cin >> temp >> temp2;
		myMultimap.insert(make_pair(temp2, temp));
		N--;

		if (maxDay < temp){ maxDay = temp; }
	}
}

void GreedAlgorithm()
{
	int sequence = curDay;
	while (curDay <= maxDay )
	{
		for (iter = myMultimap.begin(); iter != myMultimap.end();iter++)
		{
			if (curDay > maxDay){ break; }

			if (sequence < iter->second && iter->second > curDay)
			{
				sequence++; 
				continue;
			}

			if (curDay > iter->second){ 
				myMultimap.erase(iter);
				sequence = curDay;
				iter = myMultimap.begin();
				break; }

			if (sequence >= iter->second)
			{
				curDay++;
				sequence = curDay;
				result += iter->first; 

				if (myMultimap.empty()){ break; }

				myMultimap.erase(iter);
				iter = myMultimap.begin();
				break;
			}
		}

		if (myMultimap.empty()){ break; }
	}
}

int main()
{
	Initailization();
	GreedAlgorithm();

	cout << result;
	return 0;
}

음…..
로직은 실패

이번에는 과제의 마감 일이 높은 순서부터 접근
우선 큐를 사용하여 정렬한다.

입력 확인 코드

#include <iostream>
#include <queue>

using namespace std;

priority_queue<pair<int, int>> myPriorityQueue;

int N, temp, temp2, taskDeadlineMax;
pair<int, int> myPair;

void Initailization()
{
	cin >> N;
	while (N > 0)
	{
		cin >> temp >> temp2;

		myPriorityQueue.push(make_pair(temp, temp2));

		if (taskDeadlineMax < temp){ taskDeadlineMax = temp; }

		N--;
	}
}

int main()
{
	Initailization();

	while (!myPriorityQueue.empty())
	{
		myPair = myPriorityQueue.top();
		myPriorityQueue.pop();
		cout << "강의 마감일 : " << myPair.first << " 강의 점수 : " << myPair.second << "\n";
	}

	return 0;
}

1. 우선 큐에 과제를 마감일 기준으로 내림차순으로 정렬
+ 점수만 보관할 내림차순의 우선 큐를 만들어 놓는다.

2. 가장 마지막 마감 일을 기준으로 과제를 꺼내고 점수만 큐에 넣는다.
(해당 날짜의 모든 과제의 점수를 넣는다.)

3. 점수 큐에서 가장 높은 점수를 꺼내서 결과에 넣어준다.

4. 마감일이 0 이 될 때까지 반복해준다.

입력 확인 코드

#include <iostream>
#include <queue>

using namespace std;

// 과제의 마감일을 기준으로 내림차순으로 정렬
priority_queue<pair<int, int>> PriorityQueue_DeadLine_Value;

// 과제의 점수를 기준으로 내림차순 정렬
priority_queue<int> PriorityQueue_Value;

int N, temp, temp2, taskDeadlineMax, result;
pair<int, int> myPair;

// 입력 초기화를 받는 부분
void Initailization()
{
	cin >> N;
	while (N > 0)
	{
		cin >> temp >> temp2;

		PriorityQueue_DeadLine_Value.push(make_pair(temp, temp2));

		// 과제 중에서 가장 높은 마감일 값을 찾는다.
		if (taskDeadlineMax < temp){ taskDeadlineMax = temp; }

		N--;
	}
}

void Recursive(int cuurentDay)
{
	// 만약 기준 날이 0 이면 리턴해서 결과 출력
	if (cuurentDay == 0){ return; }

	// 마감일 기준으로 정렬된 과제들 중에서 
	// 기준날과 같은 과제의 점수들만 다른 우선 큐에 담아둔다(점수 내림차순)
	while (!PriorityQueue_DeadLine_Value.empty())
	{
		myPair = PriorityQueue_DeadLine_Value.top();
		if (cuurentDay == myPair.first)
		{
			PriorityQueue_Value.push(myPair.second);
			PriorityQueue_DeadLine_Value.pop();
			continue;
		}
		break;
	}

	// 점수를 담아둔 큐에서 1개만 꺼내서 결과에 더해준다.
	if(!PriorityQueue_Value.empty())
	{
		result += PriorityQueue_Value.top();
		PriorityQueue_Value.pop();
	}

	// 기준날이 0 이 될때까지 재귀를 사용
	Recursive(cuurentDay - 1);
}

int main()
{

	Initailization();
	// 재귀 시작
	Recursive(taskDeadlineMax);
	cout << result;
	return 0;
}