#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Pay
{
int pay, day;
Pay(int x, int y) // 구조체 생성자
{
pay = x;
day = y;
}
bool operator<(const Pay &x)const // 구조체 정렬기준을 연산자 오버로딩으로 구현
{
return day > x.day; // day = this.day , x.day = Pay x의 day
}
};
int main()
{
int n, d, m, j = 0, max = 0, answer = 0;
scanf("%d", &n);
vector<Pay> allPay;
priority_queue<int> pQ;
for(int i = 1; i <= n; i++)
{
scanf("%d %d", &m, &d);
allPay.push_back(Pay(m, d));
if(max < d) // 제일 긴 날짜 설정
max = d;
}
sort(allPay.begin(), allPay.end());
for(int i = max; i >= 1; i--) // 3일차부터
{
for(; j < allPay.size(); j++) // 매우 중요한 부분!! j를 계속해서 0으로 초기화하지 않는다
// 잠시 break 되었다가 break된 지점부터 다시 시작하는 방식이다.
{
Pay a = allPay[j];
if(a.day < i)
break;
pQ.push(a.pay);
}
if(!pQ.empty())
{
answer += pQ.top();
pQ.pop();
}
}
printf("%d", answer);
return 0;
}
1. 이 문제에서는 여러 쌍의 변수를 갖는 구조체 struct 을 사용하였다. vector의 pair를 사용해도 되지만, 구조체에서는 연산자 오버로딩을 활용해서 구조체의 데이터를 내가 어떻게 구현하느냐에 따라서 정렬할 수 있다.
struct Pay
{
int pay, day;
Pay(int x, int y)
{
pay = x;
day = y;
}
bool operator<(const Pay &x)const
{
return day > x.day;
}
};
2. 연산자 오버로딩을 사용할 때는 operator<(Pay &x) 와 같은 형태로 사용한다. 이 멤버 함수의 매개변수는 구조체의 주소로 받는다.
- bool operator(const Pay &x) : 구조체 x에 의해서 원본을 임의로 변경 불
- bool operator(const Pay &x) const : 이 멤버 함수가 구조체 x의 멤버 변수를 임의로 변경 불가