n개의 강연이 있으며
n개의 강연은 d (day) 와 p (pay) 가 입력으로 주어진다.
하루에 최대 한 곳에서만 강연이 가능할때, 최대로 벌 수 있는 돈은 얼마인가?
Solution
문제를 정리해보자면 한정된 날짜에 한해 가장 높은 가치를 지닌 강연을 골라야한다.
예를들어 d가 각각 1,2,3 인 강연 (x,y,z) 이 있다고 해보자.
이럴때에는 첫째날 강연에 x,y,z 강연 모두 할 수 있다.
둘째날에는 x강연은 약속기한이 지났으므로 y,z,강연만 가능하다.
똑같은 이유로 셋째날에는 z강연만 가능하다.
이 상황에서 베스트는 당연히 첫째날에는 x, 둘째날에는 y, 셋째날에는 z 강연을 하는것이다.
z를 기준으로 본다면 첫째날, 둘째날에도 가능은 하지만 x나y에 비해서 날짜의 여유가 있기때문에 마지막에 하는것이다 -> 3일째에는 z밖에 하지못한다
그 뜻은 각 강연들은 여유기간을 꽉! 채워서 '마지막날' 에 강연을 하는것이 베스트라는 뜻이다.
이 때 d가 같은 강연이라고 한다면 그때는 당연히 p가 높은 강연을 가면 되는것이다.
위에 3일째에는 z밖에 하지못한다고 말했는데 이렇게 날짜를 1일부터가 아닌 뒤에서부터 접근하게 된다면 날짜마다 강연을 한정할 수 있다.
예제를 한 번 보자.
Input
8
20 1
2 1
10 3
100 2
45 10
8 2
5 20
50 10
우선 우리는 날짜를 뒤에서부터 접근하기로 했으니 날짜를 기준으로 내림차순을 해보자.
d p
20 5
10 50
10 45
3 10
2 100
2 8
1 20
1 2
앞쪽에서 설명했던거와 연결해서 설명하자면,
p가 5인, 최대 20일의 여유가 있는 강연은 20일에 하는것이 가장 베스트다. 20일에는 다른 강연을 애초에 못하니까!
이후에 10일째에 할 수 있는 강연이 두개가 겹쳐있다. 이럴때에는 가치가 더 높은 강연(p가 50인)을 고르게 된다.
이후에 그러면 p가 45인 강연은 버리고 3일째로 가게된다고 착각할 수 있는데,
10다음에는 9일째로 가게되기에 이때는 d가 9인 강연이 없기에 비교할 필요도 없고, 강연 일정도 비어있는 상태이다. 그렇다면 p가 45인 강연을 그냥 9일째에 하면 된다. 최대가 10이니 그보다 작은 날짜에는 언제해도 상관없기 때문이다.
이후의 강연들도 똑같은 식으로 해결해주면 된다.
Code
#include <bits/stdc++.h>
using namespace std;
struct perform {
int p, d; // pay, day
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<perform> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].p >> a[i].d;
}
sort(a.begin(), a.end(), [](perform a, perform b) {
return a.d > b.d; }); //날짜를 내림차순으로 정렬
priority_queue<int> pq; //최대 강연날짜가 같을때 p가 높은값을 취하고 싶기에 heap을 이용한다.
long long ans = 0;
int k = 0; //강연의 개수를 체크해주는 변수
for (int i = 10000; i >= 1; i--) {
while (k < n && a[k].d == i) { //i가 최대강연 날짜라면
pq.push(a[k].p); //힙에 넣어준다.
k += 1;
}
if (!pq.empty()) {
ans += pq.top(); // i의 날에 가능한 가장 가치가 큰 강연을 한다. (max haep)
pq.pop();//강연을 했다면 힙에서 삭제해준다.
}
}
cout << ans << '\n';
return 0;
}참고 : https://code.plus/course/43 , 그리디 알고리즘
