- 네이버 블로그 고
언제사용?
- 최적의 해, 최대값? 최소값에 만족하는 경우를 구할 때
- 시간복잡도가 어마무시할때 생각해볼 수 있음.
그리디
: 어떤 로직이 될것 같은데, 반례에서 안될것 같음?>?>?
일단 sort랑 priority_queue 를 사용
풀이 전략
- 비교되는 원소와 컨테이너 간을 확인하면서 pq에 집어 넣고,
이후에 오는 값에 대한 반례에 대해 생각을 해야함.
-> 반드시 비교되는 원소에서 최대값을 얻기 위해 pq를 한개만
남겨야 할 필요는 없음.
관련 문제
1) 보석도둑
https://velog.io/@kwt0124/%EA%B7%B8%EB%A6%AC%EB%94%94-1202-%EB%B3%B4%EC%84%9D-%EB%8F%84%EB%91%91-fe65jw7d
🔥🔥🔥