priority queue2 [백준/C++] #1202 보석 도둑 (Greedy) 문제https://www.acmicpc.net/problem/1202 구상k개의 가방을 가지고 있고, 각 가방에 최대 무게 c만큼의 보석 1개를 넣을 수 있는 문제였다. 이때, 가방에 넣어서 훔칠 보석의 최대 가격을 구하는 문제였는데, c무게보다 같거나 가벼운 보석중에 가장 가치가 큰 보석을 하나씩 골라 가방을 하나씩 채워나가면 된다. 그러기 위해서는 우선, 보석 무게와 가방 무게를 오름차순으로 정렬해야 했다. 이후, 가방을 하나씩 돌면서, 가방 무게보다 작은 무게의 보석들을 보면서 가치 하나하나를 max_heap에 넣은뒤, 가방 무게를 초과하기 직전 상태에서 max_heap의 top 가치를 total_value에 넣어야 한다. 중복되는 보석을 max_heap에 넣으면 안되기에 넣을 보석의 인덱스를 .. 2024. 7. 15. [백준/C++] #11000 강의실 배정 (Greedy) 문제https://www.acmicpc.net/problem/11000 구상가장 처음에 왼쪽 그림처럼 2차원 배열을 만들어서 1번 강의실부터 시간들 채워나가며 몇번 강의실까지 사용하는지 알고자 했는데, S와 T의 범위가 10^9로 굉장히 커서 시간 복잡도에서 문제가 생겼다. 그래서 오른쪽 그림과 같은 구상을 했는데, 먼저, 주어진 S와 T를 배열에 넣고, S(시작 시간)기준으로 정렬한다. 그리고, 끝시간은 최소힙에 하나씩 넣고 시작시간과 비교해 시작시간이 최소힙에 있는 끝시간보다 같거나 크면 힙의 top값을 pop하고, 현재 강의 시간의 끝 시간을 최소힙에 넣는다. 남아있는 강의들 중에서 시작 시간이 가장 빠른 강의가 이미 배정된 강의 중에서 가장 끝시간이 빠른 강의 뒤에 올 수 있는지 판단하는 것이.. 2024. 7. 15. 이전 1 다음
