알고리즘 분류
- 그리디
- 우선순위
문제를 보고 생각해야 할 부분 241029
- 이러한 반례를 생각해내는 것이 관건이다!!!!! 정말 중요!
2일 동안 강의 순회가 가능하다고 하자.
day pay
1 10
2 20
3 40
이라고 한다면? -> 2 20 / 3 40 을 선택하는 것이 최고의 탐욕이다!!
- 우리가 구하고자 하는 거는 최대값을 구하는건데
최대값을 얻는 방법은 2개를 생각해야 한다.
1) 최소를 줄이거나
2) 최대를 늘리거나.
-> 데이터를 삽입시 위 2개를 적용하기 위해서 최소를 선택하지 않는 것을 확인할 수 있다.
최근 풀이 241030
https://www.acmicpc.net/submit/2109/85790490
언제품 ?
: 220913 17:16 ~ 17:43
정답 풀이 전략
- 반례에 대해서 생각을 해보자.
// 1 1
// 5 1
//20 1
//200 3
//150 3
//100 2
// 80 2
// 80 6
// 70 6
이러한 값이 있다고 한다면?
답은 70 + 80 + 100 + 150 + 200 이다.
왱???
d는 d일 내에 와서 강의를 해주면 되기 때문에 d가 3이라는 것은
1일차, 2일차, 아니면 3일차에 와서 해주기만 하면됨.
만약 d가 1인 친구의 pay가 40 이고, d가 3 잡힌 게 3개 있는데
40보다 3개가 모두 크다고 한다면?
당연히 d가 3인 3개를 모두 선택하는 것이 이득!!
- 어떻게 전략을 만들 것인가에 대해?
설정값 : pq에서 가장 작은 것을 빼기 위해 작은것을 top으로.
확실한건 위의 예에서 d가 1인값이 2개 있는데 , 1일 사이에
1) 해결해야 하므로, 큐에서 가장 작은 것이 top에 위치시킨 상태로 만듦.
2) 그리고 큐에 2개를 집어 넣음
3) 근데 1일만에 2개를 모두 할 수는 없으므로 가장 작은 top을
pop하자.
-> 구현은 pq.size() > day 라면 , day의 갯수에 맞출때까지
pq.pop()을 진행하자.
4) 2일차 2개를 위와 동일한 루틴으로 넣어보면,
q : 20 80 100 이 들어가 있음.
근데 2일 만에 3개의 강의를 모두 할수는 없음!
->결과 : 가장 작은 top에 있는 20을 제거하자.
5) 3일차는 2개 있음. 200 150 , 큐에 삽입하면?
q: 80 100 150 200임. 마찬가지로 size > 3 이므로 1개 제거
-> 결과 : 100 150 200
~~ 이런식으로 진행해야 겠다는 판단을 햇고, 코드를 짬!
최종 코드
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#include <queue>
// 2109번. 순회 강연
// 12: 05 ~ 12:48
int main(void)
{
// 하루에 최대 한곳에서만 강연 할 수 있음.
// 가장 큰 돈을 벌어야 함.
// 일단 동일한 d오름 차순으로 정렬을 하고,
// 동일한 값에서 가장 큰 돈을 뽑음.
// 20 100 10 5 50
// 이라고 했을 때
// 200 300 150 이 가장 적합 한듯함.
// 동일한 d에서 가장 큰 p값을 맨위로 올림.
// 큐에 집어넣을 때 기존값보다 p가 작으면 아예 삽입 하지 말자?
// d가 2라면 . 사이즈에 2개가 들어가야 함.
// 기존에 넣은 갑보다 이후에 들어오는 p가 더 크면,
// 기존 값을 pop한 다음에 넣자. 작으면 일단 push?
// d가 1일 경우에 20 ,
// d가 2일 경우에 기존 q에 20이 들어가 있는데
// d가 2이므로 최종적으로 사이즈가 2이어야 함.
// q에 100 80 20 넣고,
// d가 3이므로 , 200 150 100 80
// 에서 마지막에
int n;
cin >> n;
vector<pair<int, int>>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i].second >> v[i].first;
}
sort(v.begin(), v.end());
//for (int i = 0; i < n; ++i)
//{
// cout << v[i].first << " " << v[i].second << endl;
//}
priority_queue<int, vector<int>, greater<int>>pq;
// 확인용
//for (int i = 0; i < n; ++i)
//{
// //일단은 동일한 d값에 대해서만 진행을 해야함.
// int value = v[i].first;
//
// pq.push(v[i].second);
//
//
//
//}
//cout << pq.top() << endl;
for (int i = 0; i < n; ++i)
{
int day = v[i].first;
pq.push(v[i].second);
while (pq.size() > day)
{
pq.pop();
}
}
int res = 0;
while (!pq.empty())
{
res += pq.top();
pq.pop();
}
cout << res;
// 1 1
// 5 1
//20 1
//200 3
//150 3
//100 2
// 80 2
// 80 6
// 70 6
// 20 80 100
// 80 100
// 80 100 150
// 80 100 150 200
// 100 150 200
// 80 100 150 200
// 70 80 100 150 200
}
// 100 8 2
// 100 8
// 100 10 8
// 100 50 10 8
// 100 50 20 10 8 
뭐가 문제였을까?
: 문제에서 의도하는 바를 잘못 캐치함.
/*
3
1 1
10 2
10 2
// 반례 : 20
-> 이럴 경우, 나는 11로 생각했지만,
잘못된 생각임.
2일 내도 2일차 10값 2개를 하면 되자나!
*/
1번째 풀이
#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
#include <map>
bool func(pair<int, int> p1, pair<int, int>p2)
{
if (p1.first < p2.first)
{
if (p1.second > p2.second)
return true;
return true;
}
return false;
}
int main()
{
// 문제를 괜히 어렵게 만든듯함.
// d, p
// 2 50
// 1 10
// 2 20
// 1 30
// d일 안에 와서 강연만 하면 됨.
// => d를 기준으로 오름 차순으로 정렬한 다음에
// cnt를 카운팅 하면서 cnt pair에서 가장 큰값을 추출한 다음에
// sum하자
// 1 2 3 10 20
// 20 100 10 50 5
int n;
cin >> n;
int p, d;
vector<pair<int, int>>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i].second >> v[i].first;
}
sort(v.begin(), v.end());
/*
for (int i = 0; i < n; ++i)
{
cout << "first : " << v[i].first << "second : " << v[i].second << endl;
}
*/
int sum = 0;
map<int, int>m;
for (auto iter : v)
{
m[iter.first] = iter.second;
}
/*
cout << "hello" << endl;
for (auto iter : m)
{
cout << iter.first << " " << iter.second << endl;;
}
*/
for (auto iter : m)
{
sum += iter.second;
}
cout << sum;
}
-> 7퍼센트에서 틀림.
왜 틀렸을까?
반례가 있음.
3
1 1
10 2
10 2
// 반례 : 20
