hades

🥅 문제https://www.acmicpc.net/problem/1766 🔍 설계먼저 푸는 것이 좋은 문제를 먼저 푼다는 것에서 두 문제 간의 순서가 정해져 있고, 위상 정렬임을 쉽게 파악할 수 있었다. 추가로 우선순위가 같은 경우, 쉬운 문제를 먼저 풀기 때문에 진입 차수가 0이 되었을 때, 바로 출력하지 말고, greater 우선순위 큐를 이용하여 진입 차수가 0인 문제 번호를 담아 빼낼 때마다 출력하도록 한다. 👊 풀이#include #include #include #include #include using namespace std;int n, m, a, b;priority_queue, greater> pq;vector degree(100001);vector> adj_list(100001);v..

🥅 문제https://www.acmicpc.net/problem/1202 🔍 설계가방에는 가방이 담을 수 있는 무게 이하의 보석만 담을 수 있다. 보석을 어떻게 담을지가 문제다. 보석과 가방의 무게를 오름차순으로 정렬하고, 가방마다 담을 수 있는 보석 중 최대 가치를 결과에 더하면 된다.  최대 가치는 우선순위 큐를 이용하여 구한다. 탐색하는 보석에 대하여 인덱스를 공유하면, O(N+K)로 해결할 수 있고, 우선순위 큐를 공유함으로써 그 가방 최대 무게 이하의 보석을 고려할 수 있다. 👊 풀이#include #include #include #include using namespace std;int n, k, m, v, c, p = 0;long long result = 0;vector> jewel;v..

🥅 문제https://www.acmicpc.net/problem/11286 🔍 설계우선순위 큐를 사용하여 첫 번째 조건으로 절댓값을 비교하고, 두 번째 조건으로 절댓값이 같다면 실제 값을 비교하여 작은 것이 우선순위가 높도록 한다. 👊 풀이#include #include #include using namespace std;int n, x;struct compare { bool operator()(int a, int b) { if (abs(a) > abs(b)) { return true; } else if (abs(a) == abs(b)) { return a > b; } else { return false; } }};priority_queue, compare> pq;int mai..

🥅 문제https://www.acmicpc.net/problem/7662 🔍 설계처음에 min_pq와 max_pq만을 만들어서 D일 때 n이 무엇이냐에 따라 한쪽으로 몰아서 처리하는 방식을 택했는데 시간 초과가 발생했다. 다른 방법을 찾아야 한다. map을 이용하여 개수를 저장하고, D일 때, 삭제를 하기 전, 다른 명령에서 개수가 0이 되었을 수도 있으므로 그 경우를 고려하여 삭제 처리를 해주어야 한다. 예를 들어 D 1이어서 max_pq에서는 삭제했지만, min_pq에서는 삭제할 수 없으므로 반영되지 않았다. 개수만 감소시키고, 삭제하려는 수의 개수가 0일 때, 모두 삭제한다. 👊 풀이#include #include #include using namespace std;char ch;int t, ..