Priority Queue

[백준] 13904. 과제 - 파이썬

[Gold III] https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 Greedy와 Priority Queue를 적절히 이용해 풀 수 있었던 문제. 입력된 과제를 점수(value) 순으로 정렬하고, 점수가 높은 것부터 Greedy하게 몇일차에 풀 지 배치. 7 4 60 4 40 1 20 2 50 3 30 4 10 6 5 와 같은 예제 입력에서는, 점수 순으로 정렬했을 때 아래와 같아진다. 4 60 2 50 4 40 3 30 1 20 4 10 6 5 맨 위(점수가 가장 높은것)부터 하나..

[백준] 1202. 보석 도둑 - 파이썬

[Gold II] https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 1 담을 수 있는 보석의 value를 최대로 해야 하므로, 일단은 우선순위 큐 (최대 힙)을 이용할 것이라 생각했음. 우선 생각나는 대로 먼저 구현해 보았고, line 18 ~ line 33 쪽에서 가방에 들어갈 수 있는 지 Brute-Force로 반복해가며 검사했기 때문에, 아마 TLE(시간초과)가 나올 것이라고..