https://www.acmicpc.net/problem/1202 가방은 오름차순으로 정렬한다.가장 가벼운 가방으로 들 수 있는 보석들은 이후 모든 가방으로도 들 수 있기 때문이다. 보석은 무게를 기준으로 오름차순으로 정렬하되, 무게가 같은 경우, 가격순으로 내림차순으로 정렬한다.훔칠 수 있는 보석 가격의 합의 최댓값을 구해야 하기 때문이다. 가방을 모두 순회하며 해당 가방의 무게로 들 수 있는 보석들을 우선순위 큐에 저장한다.우선순위 큐는 무게와 상관없이 가격순으로 내림차순 정렬이 되도록 한다. 현재 가방 무게로 가장 비싼 보석을 더하고, 큐에서 제거한다.#include #include #include #include using namespace std;bool Cmp(const pair& a, con..
우선순위 큐
https://www.acmicpc.net/problem/17420 사용하려는 날보다 이전 날에 사용한 기프티콘의 유효 기간보다 커야 한다는 점을 유의한다.기프티콘 사용 계획을 오름차순으로 정렬하여, 먼저 사용하는 순서대로 로직을 설계한다. 다음 예시를 통해 설명한다.424 2 3 29 // 기프티콘 유효 기간25 30 30 30 // 사용하려는 날 ans: 6 남은 기프티콘의 유효 기간이 짧은 순서대로 사용해야 한다하지만, 30일에 사용하는 2, 3, 24의 경우, 아직 25일이 지나지 않았기 때문에, 사용하지 못한다. 그러면 사용하려는 날을 기준으로 계산해 보자.사용하려는 날을 오름차순으로 정렬한다. 25일을 보자.현재 날짜가 25일이면, 사용할 수 있는 기프티콘으로는 24가 있다.기프티콘..
https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 먼저, 모든 작업을 처리한, 총 ms를 구한다.(기저사항, 모든 작업이 끝났는지 확인하기 위함) 요청은 무조건 먼저 들어오는 순으로 받아야 하기 때문에, 요청 시간을 기준으로 오름차순으로 정렬한다.현재 시간과 현재 처리 중인 요청을 저장할 변수를 선언한다.더 처리할 요청이 남아있고, 현재 시간에 요청이 있을 경우, 큐에 { 수행 시간, 요청 시간 }으로 넣는다.이러면, 새 데이터가 들어오면 우선순위 큐에서 수행 시간을 기준으로 오름차순으로 정렬..
문제: https://www.acmicpc.net/problem/1781 최대 데드라인을 초과하지 않는 범위에서 가장 많은 컵라면을 얻는 문제이다. ex)7 1 9 1 100 2 300 2 99 3 100 5 100 5 999 다음 예시에서, Day1에서는 1~5 데드라인의 문제를 모두 풀 수 있다.그리고, Day5에서는 5 데드라인의 문제만이 풀 수 있다. 따라서, 이 문제는 마지막 날부터 역순으로 계산하는 것이 핵심인 문제이다. 데드라인을 하나씩 줄여가며, 각 날짜에 풀 수 있는 문제들을 우선순위 큐에 넣는다.(우선순위 큐는 그러면 계속 풀 수 있는 문제 후보군들이 남아있다)각 날마다 우선순위 큐 안에서 보상이 가장 큰 문제를 선택하여 정답에 더하고, 큐에서 뺀다.#include #include #i..
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net #include #include #include #include using namespace std; int N, E, V1, V2, Cnt; map m; vector Dist, SaveDist; void Dijkstra(int start) { priority_queue pq; pq.push({ 0, start }); Dist[start] = 0; wh..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net #include #include #include #include using namespace std; int N, M, X, Cnt; map m; vector D1, D2; int Dijkstra(int start, int dest) { priority_queue pq; vector visit(N + 1, false); vector dist(N + 1, 9876543..
