최근 풀이 : 241101

: 기존 그리디와는 다르게

오름차순으로 정렬된
bag의 무게와 gems의 무게를 비교하면서 bag보다 무게가 작거나 같은 경우에
jems의 가격과 비교를 하면서 pq에다가 넣는다.

그런데 우리가 구하는 거는 가장 높은 가격이니까.
pq에 top이 높은 가격이 올라올수 있게 디폴트로 정렬해놓자.

1) bag보다 무게가 작은 jems들을 타겟으로 해서 모두 다 pq 넣자.
2) 그러다가 가방 무게보다 높은 jems이 나오면 탈출
-> 가방 하나에 jems 1개 넣을 수 있을니까. top에 있는 하나를 뽑자.

3) 그리고 이제 bag 의 인덱스를 하나 증가해서 그거랑 다음번에 있는 gems를 비교한다.

---

😜최근 풀이 : 240205

: 내 생각에는 가방이랑 보석 둘다 무게를 가장 오름차순으로 정렬을 한 상태에서 진행하고자 함.

내가 왜 이렇게 생각했냐면?

1 10
1 9
1 5
3 50
5 4
10 100
이렇게 보석이 있고,
가방은 1개 인데 무게가 3짜리가 있다고 하자.

• 그러면 굳이 보석 (5,4) (10 , 100) 에 관해서는 처리를 할 필요가 없기 때문임.

가방에다가 입력할 때부터 pair< 무게 , 가격 제일 큰거> 로 넣기 위해 pq를 이런식으로 구성함.
priority_queue<pair<int,int> ,
vector<pair<int,int>>, compare > pq;

• 1 65
• 2 99
• 5 23
  으로 정렬 한 상태에서
  가방도 2 10 이렇게 정렬 되겠지

  잘못생각한 부분.

  가방 전체 갯수만큼 for문을 돌리면서 즉 가방의 무게가 2일 때
  가방 2개를 체크할 수 있음. (1 ,65) , (2, 99) -> 여기서 최대의 money를 뽑고
  가방의 무게를 10으로 변경 (5,23) 에서 최대의 money를 뽑으려고 했는데
  -> 실행하고 나서 잘못 생각했구나를 깨달음. -> 이렇게 하면 답은 122가 나옴.
  : pq를 pop 하는 방식으로 했는데 이렇게 하지 말고, 반대로 진행해야 함.

  올바른 결과

  

  변경 점.

  반대로 pq 에다가 최고값을 우선으로 해서 누적했다가 가방의 갯수만큼
  pq.pop() 해야겠다고 생각.

#include <iostream>
using namespace std;


#include <vector>
#include <queue>

struct compare
{
	bool operator()(pair<int,int>& a, pair<int,int>& b)
	{
		if (a.first == b.first)
		{
			return a.second < b.second;
		}
		else
			return a.first > b.first;
	}
};


int main()
{
	int n, k;

	cin >> n >> k;

	priority_queue<pair<int,int> ,
	vector<pair<int,int>>, compare > pq;
	//vector<gem> gems(n);
	// 각 보석 n개는무게 m과 가격 v를 가지고 있음.
	int a, b;
	for (int i = 0; i < n; ++i)
	{
		cin >> a >> b;
		pq.push(make_pair(a, b));
	}

	//while (!pq.empty())
	//{
	//	auto iter = pq.top();
	//	pq.pop();
	//
	//	//cout << iter.first << "  " << iter.second << endl;
	//}

	// 상덕이가 훔칠수 있는 보석 가격의 합의 최대값.

	vector<int> bags(k);
	for (int i = 0; i < k; ++i)
	{
		cin >> bags[i];
	}
	sort(bags.begin(), bags.end());
	//for (int i = 0; i < bags.size(); ++i)
	//{
	//	cout << bags[i] << endl;
	//}
	// 무게가 아니라, 최대의 보석 가격이니까. 
	// money 위주로 정렬을 시키자. 그러면서 
	// 

	// bags 도 무게가 가장 작은 것을 위치하자.

	// 무게가 작을수록 더 많은 보석을 담을 수 있기 때문임. 

	// 앗 가방에는 최대 한개의 보석만 넣을 수 있다. 

	// 30만 * 30만 -> 30 30 10000 10000 -> 900 100000000

	// 1 65
	// 2 99
	
	// 2 

	// 30만 30만 돌리기에는 시간복잡도 초과이니까
	// pq에다가 넣으면 최고의 상태를 뽑아다 확인하는 식으로 핮.

	// 무게 위주로 해야겠다.
	// 가방도 낮게 설정하자.

	// 무게로 가자. 
	// 가방의 무게랑 gem 의 무게를 비교하면서
	// 동일할때까지 진행하면서 최고의 수단을 뽑자. 
	// -> 가격이 최대인거를 얻자. 
	int ret = 0;
	for (int i = 0; i < bags.size(); ++i)
	{
		int mmax = -1;
		// 가방 맨앞의 인덱스를 타겟으로 해서
		// pq 뺑뺑이 돌리면서 최대의 money를 얻자. 

		
		{
			while (!pq.empty() && pq.top().first <= bags[i])
			{
				auto iter = pq.top();
				pq.pop();

				if (mmax < iter.second)
				{
					mmax = iter.second;
				}

			}
		}
		

		if(mmax != -1)
			ret += mmax;	

	}
	cout << ret << endl;
}

2번째 풀이 : 240205

: bags의 for문 돌릴 때 pq에 넣는 방식으로 진행하고자함.
조건에 해당할 경우, pq에다가 넣자.
-> 하다 보니까 index만큼 while 문 돌리기 위한 조건식 추가됨.
넣은 후에 최고의 money가 위에 올라와 있는 상태에서 bags의 갯수만큼만 ret에 넣는 방식으로 진행하고자 함.

-> 이렇게 하면 3퍼센트에서 틀림.
: 틀린 코드는 외부에서 while문 돌리면서 누적하는 부분이다.

중요! 왜 여기서 문제냐...

왜 여기서 문제가 발생하느냐에 대해서...
나처럼 하게 되면, 조건식이 추가되고,
또 다시 pq에 넣어진 값에 대한 시간복잡도가 추가됨. pq에 총 30만개 들어갈 수 있음.
(문제 조건식에 의해) , 이렇게 처리하면 시간복잡도 최악에 30만이 추가됨.
-> 차라리 위 bags의 for문에서 처리하면 시간복잡도 pq.pop() 1로 처리할 수 있음.
이렇게 처리하면 30만을 아낄 수 있음.

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

#include <vector>
#include <queue>

struct compare
{
	bool operator()(pair<int,int>& a, pair<int,int>& b)
	{
		if (a.first == b.first)
		{
			return a.second < b.second;
		}
		else
			return a.first > b.first;
	}
};


int main()
{
	int n, k;

	cin >> n >> k;

	vector<pair<long long, long long>> gems(n);
	// 각 보석 n개는무게 m과 가격 v를 가지고 있음.
	int a, b;
	for (long long i = 0; i < n; ++i)
	{
		cin >> gems[i].first;
		cin >> gems[i].second;
	}
	sort(gems.begin(), gems.end());
	
	vector<long long> bags(k);
	for (long long i = 0; i < k; ++i)
	{
		cin >> bags[i];
	}
	sort(bags.begin(), bags.end());
	
	long long ret = 0;
	long long index = 0;
	long long cnt = 0;
	priority_queue<long long> pq;
	for (long long i = 0; i < bags.size(); ++i)
	{
		int mmax = -1;
		
		while (index < gems.size() 
			&& bags[i] >= gems[index].first)
		{
			pq.push(gems[index].second);
			index++;

			if (index >= gems.size())
				break;
		}
		

		//if (!pq.empty())
		//{
		//	ret += pq.top();
		//	pq.pop();
		//}
	}
	
	while (!pq.empty())
	{
		//cout << pq.top() << endl;
		ret += pq.top();
		pq.pop();
		cnt++;
		if (cnt == bags.size())
			break;
	}
	cout << ret << endl;
}

3번째 풀이 : 240205

https://www.acmicpc.net/submit/1202/72976274

---

이전 풀이... 😜맞왜틀??

✨ 7 퍼센트에서 틀림.

: 우선순위큐를 top이 낮게 설정을 하고, bag의 갯수에 맞지 않다면?
pop을 한 후, 한번에 더하는 방식으로 햇음.
-> 7퍼센트에서 틀림.

: 두개로 분류했더니 틀림..

시간 복잡도를 먼저 생각해보자.

• 이 생각도 맞지만, 이렇게 하게 될 경우, pq에 넣는 부분과
  sum에 누적하는 부분을 나뉘어서 처리를 해야함.
  -> pq에 보석의 최대 개수 30만이 들어갈 수 있음.
  분리해서 하면 30만번의 시간복잡도가 추가되는 것임.

💥50퍼센트에서 틀림.

• 조건식 처리 안하면. 틀림.
  : 동그라미 부분 처리하니까 맞음.
  

핵심

: 문제의 관건이 가장 큰 값을 구하는 것이기 때문에
가방 하나 완료될때마다 가장 큰값 하나만 추출하자!

• 중간단계 거치지 않고, 바로 접근할 수 잇는지를 확인하자.

맞는 풀이

: 위의 생각보다는 pq의 top에 최대값으로 설정을 하고,
가방 무게 초과할 경우, 그 부분에서 한번만 누적하는 조건으로 하는
것이 오히려 효율적임.

• 접근방법 1번 : pq를 낮게.
  가방 무게 : 2, 10
  보석 1-65 , 2-99 , 5-23에서
  가방 무게 2 종료 : top : 65 99
  가방 무게 10 종료 : top : 23 65 99
  bag의 for문 끝나고 bag의 사이즈 (2개) 에 맞춰서 pq.pop을 한번만 하기
  -> 65 , 99를 누적함.

• 접근방법 2번 : pq를 높게
  가방 무게 : 2, 10
  보석 1-65 , 2-99 , 5-23에서
  가방 무게 2종료 : top : 99 65
  -> 조건문 마치고, 가장 큰 99를 누적시킴
  가방 무게 10 종료 : top : 65 23
  -> 조건문 마치고 가장 큰 65를 누적시킴.

=> 무엇이 더 효율적이 시퀀스일까? 를 생각하면 , 접근 방법 2번이
훨씬 효율적이라는 것을 생각할 수 있음.

---

1번째 풀이전략

// 풀이전략
// 1. pair 값을 money 내림차순으로 정렬하자
// 왜냐하면? 가장 큰 보석 가격합을 구하는 것이므로.
// 2. 가장 큰 money를 뽑기 위해서
// 가방의 무게는 가장 큰 값을 위로 올리자. 즉, 내림 차순으로
// 왜냐하면? 논리적으로 생각해보면, money가 가장 큰값이
// 무게가 클 수 있기 때문임.

그런데 이렇게 하면 . 7%에서 틀림.
-> 다른 방법을 생각해보자. 그리고 왜 틀렸는지 생각해보자.

우디르급 태세 전환이 필요함.
--> 정렬과 pq를 사용하자.

1번째 풀이 : pq 사용안하고, 1번째로 풀었을 때

-> 7%에서 틀림.

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



int main()
{
	//30만 30만 

	// 23 5
	// 65 1
	// 99 2

	// 99 2
	// 65 1
	// 23 5

	// 1 65
	// 2 99
	// 5 23

	// 5 23
	// 2 99 
	// 1 65
	
	// 2 
	//10

	// 10
	// 2
	
	// 풀이전략 
	// 1. pair 값을 money 내림차순으로 정렬하자
	// 왜냐하면? 가장 큰 보석 가격합을 구하는 것이므로.
	// 2. 가장 큰 money를 뽑기 위해서 
	// 가방의 무게는 가장 큰 값을 위로 올리자. 즉, 내림 차순으로 
	// 왜냐하면? 논리적으로 생각해보면, money가 가장 큰값이
	// 무게가 클 수 있기 때문임.

	long long n, k;
	cin >> n >> k;

	vector<pair<long long, long long>>v(n);
	for (long long i = 0; i < n; ++i)
	{
		cin >> v[i].second >> v[i].first;
	}

	sort(v.begin(), v.end(), greater<pair<long long, long long>>());

	//cout << "보석의 무게와 " << endl;
	//for (auto iter : v)
	//{
	//	cout << iter.first << ' ' << iter.second << endl;
	//}

	vector<long long >bag(k);
	// 가방의 무게 입력하자.
	for (long long i = 0; i < k; ++i)
	{
		cin >> bag[i];
	}

	// 가방의 무게를 내림차순으로 만들어야 함.
	sort(bag.begin(), bag.end(), greater<long long>());

	//for (auto iter : bag)
	//	cout << iter << endl;

	long long idx = 0;
	long long res = 0;
	//for (int i = 0; i < bag.size(); ++i)
	{
		for (long long j = 0; j < v.size(); ++j)
		{
			long long weight = v[j].second;
			if (weight < bag[idx])
			{
				++idx;
				res += v[j].first;
			}

			if (idx == bag.size())
				break;
		}
	}


	cout << res;


}

위에거 안되니까 우디르급 태세전환이 필요함!

: 내가 모르는 반례가 있는듯함.

2번째 풀이

1) 보석을 무게 - 가격 으로 해서 오름차순으로 놓자.
2) 가방의 무게도 오름차순으로 놓고.

가방의 무게보다 이하인 보석의 무게를 체크하면서 가장 큰 가격을
캐치하는 방식으로 진행하자.
-> 잘못된 생각!

• 반례 : 문제 푸는데 가장 중요한 지식
  가방의 무게 2 , 10
  보석 (2,97), (2,67) , (10,5)
  가 있다고 할 때
  가방 2에다가 넣을때 (2,97)만 넣고, (2,67)을 버리면 안됨!
  왜냐하면 그 다음에
  가방 10에다가 (10,5) 를 넣게 되면
  -> 최대값이 안나옴.
  따라서 우선순위 큐에다가 먼저 해당하는 값을 넣어놓고, pop은 안한 상태에서
  (10, 5)를 넣어놓은 상태에서 비교하자는 것임.
  우선순위 큐 특성이 가장 작은 값, 가장 큰 값을 top()에 위치시키므로
  pop의 경우는 result 값에 누적할때만 사용하자.
  만약 여기서 (2,97) 과 (2,67)을 비교해서 우선순위 큐에 (2,97) 만 넣는다면
  문제다!

알아야 할 점.

pq에 넣는다면, 가장 작은 값을 기준으로 넣으면, 나중에 큰값 비교하더라도,
이미 pq에 넣게 되므로, 문제가 없음.

주의할 점.

1. long long
2. 범위 조건 j < n;