[C++] 백준(BOJ) - 2109 : 순회 강연
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.
예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.
입력
첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.
출력
첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
알고리즘
- 그리디
- 정렬
- 우선순위 큐
풀이
- 최대값을 만들기 위해서는 최소를 적게 만들거나 최대를 크게 만드는 두 가지 방법이 있다
- Day를 내림차순으로 정렬한 경우 : 최대를 많게
- Day를 오름차순으로 정렬한 경우 : 최소를 적게
코드 1 : Day를 내림차순으로 정렬한 경우
// BOJ-2109 : 순회강연
#include<bits/stdc++.h>
using namespace std;
int n, d, p, mx = -2147000000, res = 0;
struct Data
{
int money;
int when;
Data(int a, int b)
{
money = a;
when = b;
}
bool operator<(const Data& b) const
{
return when > b.when;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
vector<Data> v;
priority_queue<int> pq;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> p >> d;
v.push_back(Data(p,d));
if (d > mx)
{
mx = d;
}
}
sort(v.begin(), v.end()); // Data 데이터 형식의 bool operator를 재정의 해 준 when 요소의 경우에는 내림차순 정렬이 되지만, money 요소는 default인 오른차순 정렬된다
int j = 0;
for (int i = mx; i >= 1; i--)
{
for (; j < n; j++)
{
//cout << "I_position : " << i << ' ';
//cout << "J_position : " << j << '\n';
// break 구문은 반복자를 ++시키지 않는다
if (v[j].when < i) break;
pq.push(v[j].money); // 가능한 일자라면 일단 집어 넣고
}
if (!pq.empty())
{
res += pq.top(); // 최대값만 더한다
pq.pop();
}
}
cout << res << '\n';
return 0;
}
코드 2 : Day를 오름차순으로 정렬한 경우
// BOJ-2109 : 순회강연
#include<bits/stdc++.h>
using namespace std;
int n, p, d, res = 0;
vector<pair<int, int>> v;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> p >> d;
v.push_back({ d,p });
}
sort(v.begin(), v.end()); // day를 기반으로 오름차순 정렬
priority_queue<int, vector<int>, greater<int>> pq; // pq.top() 값은 최소값
for (int i = 0; i < n; i++)
{
pq.push(v[i].second); // 일단 집어넣고
if (pq.size() > v[i].first) pq.pop(); // Day 겹치면 최소값 빼버리기
}
while (pq.size())
{
res += pq.top(); pq.pop();
}
cout << res << '\n';
return 0;
}
평가
- 그리디 문제는 아이디어를 기반으로 문제를 도식화하여 생각해보는 접근이 필요
- 문제를 다각도에서 보는 방식이 필요하다. 일단 해보기 -> 경험치가 많이 필요
