[C++][BOJ] 2109 순회강연 :: 그리디(Greedy)

 

[문제]

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

 

d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불한다.

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

가장 많은 돈을 벌 수 있는 순회강연을 찾고 그 돈을 출력하라.

 

 

[풀이]

d 일 안에 와서 강연이라는 조건을 d 일에 강연하는 걸로 잘못 이해하여 map 으로 풀다가 틀렸다.

게시판을 참고해보니 d 일 안에 와서 라는 조건이 있기에 d 일 안이면 언제든 강연할 수 있다는 것을 생각해야 한다.

 

n개의 대학의 전부를 비교하기에는 시간제한이 되므로 sort, priority queue 를 이용한 Greedy  로 접근해야 한다.

기한을 기준으로 할건지 강연료를 기준으로 할 건지 정렬 기준을 세워야 한다.

 

손으로 그려가며 기한 오름차순/내림차순, 강연료 오름차순/내림차순 을 해서 문제를 풀어보았을 때,

기한을 기준으로 오름차순 정렬하고, 오름차순 priority_queue로 queue 의 크기 > 비용과 비교하며 최소값을 제거하고 최대값만 남기면 풀린다.

 

 

[풀이 예시]

5

3 3

2 3

1 3

100 4

90 4

 

1) 먼저 일자를 기준으로 오름차순 정렬하기

d p

3 1

3 2

3 3

4 90

4 100

 

2) priority queue 에 넣고 priority queue 크기보다 일자가 넘지 않는지 비교한다.

priority queue 크기 자체가 기한이 되며 (1개 넣으면 1일차 이내, 2개 넣으면 2일차 이내 등)

오름차순 정렬되기에 맨 위 루트값에 최소값이 저장된다.

 

i = 0

오름차순 정렬되는 priority queue 에 1을 넣는다. priority queue size (1) < 기한(3)

 

i = 1

priority queue 에 2를 넣는다. priority queue size (2) < 기한(3)

 

i = 2

priority queue 에 3를 넣는다. priority queue size (3) == 기한(3)

 

i = 3

priority queue 에 90를 넣는다. priority queue size (4) == 기한(4)

 

i = 5

priority queue 에 100를 넣는다. priority queue size (5) > 기한(4)

맨 위에 있는 최소 강의료(1)를 뺀다.

 

 

[반례]

4

2 1

3 1

4 2 

5 2

정답 : 9

 

5
3 3
2 3
1 3
100 4
90 4
정답 : 195

 

 

[코드]

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

int universityNum, pay, day, maxPay = 0;

vector<pair<int, int>> v; // 기한, 강연료 조합을 일단 모두 담을 벡터
priority_queue<int, vector<int>, greater<int>> pq; // int형, prices(강연료), 오름차순 정렬(가장 적은 강연료가 루트에 위치)

void Input();
void SearchMaxPay();
void Output();

int main() {

	Input();
	SearchMaxPay();
	Output();

	return 0;
}

void Input(){
	cin >> universityNum;

	for (int i = 0; i < universityNum; i++){
		cin >> pay >> day;
		v.push_back({ day, pay }); // day(기한)를 기준으로 오름차순 정렬
	}
	sort(v.begin(), v.end());
}

// priority queue 오름차순 정렬 버전으로 최대비용 찾기
void SearchMaxPay() {
	for (int i = 0; i < universityNum; i++) {
		pq.push(v[i].second);// 앞 일자 기한부터 강연료 일단 넣기(오름차순 정렬됨)
		// 현재 pq 사이즈보다 일자 기한이 크면 'd일 안에 와서' 라는 조건을 만족할 수 없으므로
		// 맨위 최소값을 빼고, 더 큰값을 pq에 넣기 
		if (pq.size() > v[i].first) {
			pq.pop();
		}
	}
}

void Output() {
	while (pq.size()) {
		maxPay += pq.top(); pq.pop();
	}
	cout << maxPay << "\n";
}

 

 

map 으로 풀다가 틀린코드...

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

int main() {
	unordered_map<int, int> scheduleList; // key: day, value: price

	int universityNum, price, day, maxPrice = 0;
	cin >> universityNum;

	for (int i = 0; i < universityNum; i++) {
		cin >> price >> day;
		if (scheduleList.find(day) == scheduleList.end()) {
			scheduleList.insert({ day, price });
		}
		else {
			if (scheduleList[day] < price) {
				scheduleList[day] = price;
			}
		}
	}

	for (pair<int, int> schedule : scheduleList) {
		maxPrice += schedule.second;
	}

	cout << maxPrice;

	return 0;
}