문제
https://www.acmicpc.net/problem/1781
접근1 (틀림)
- 가장 먼저 생각한 방법은 딕셔너리를 사용해서 데드라인 별로 얻을 수 있는 컵라면을 리스트 형태로 저장한 후 정렬해서 각 데드라인 일자마다 문제 풀이가 가능한 갯수만큼 더하는 방법으로 작성
- But, 많은 컵라면을 얻을 수 있는 문제의 데드라인 값이 큰 경우, 해당 문제를 풀기 전 데드라인 값이 작은 문제들을 먼저 풀어버려서 많은 컵라면을 얻을 수 있는 문제는 못 풀게될 가능성)
접근2 (시간초과)
- 이렇게 생각하니 컵라면을 많이 얻을 수 있는 문제부터 풀어 나가면서, 그 문제를 푸는 날은 데드라인에 최대한 가까운 날로 기록해야겠다는 생각이 들었고 그리디로 문제 접근
- 주어진 날들을 반복하면서 해당 문제를 풀 수 있는지 확인하는 과정마다, 남아있는 날들 중 컵라면을 많이 얻을 수 있는 날들이 필요하기 때문에 우선순위큐를 사용해야겠다고 생각했다.
- 그래서 check 배열을 만들어서 문제를 풀 때마다 해당 문제의 데드라인과 가장 가까운 날들을 찾아서 그러한 날이 존재하는 경우에 check 배열에 기록하고 ans에 더하는 방식으로 코드 작성
- But, 최대 200000일까지 가능한 상황에서 모든 문제에 대해 문제를 풀 수 있는 날을 찾으려고 check 배열을 돌기 때문에 만약 문제를 풀 수 있는 날이 존재하지 않거나, 데드라인과 아주 멀리 떨어져 있는 날인 경우 시간초과 발생
접근3
- 여기서 병목지점은 내가 이 문제를 풀 수 있는지 확인하려고 주어진 데드라인까지의 모든 날들을 확인하는 부분
- 따라서, 가능한 날들을 저장한 배열(remain)을 만들어서 이분탐색을 통해 해당 문제의 데드라인이 배열의 어디에 들어가는지 확인해서 해당 문제를 풀 수 있는지 없는지 여부를 판별
풀이
- 주의할 점은 남아있는 날들 중에서 데드라인과 같은 날이 존재하는 경우 때문에 bisect_right를 사용했으며, 구한 idx에서 1을 빼주었다.
- heapq는 최소힙이므로 최대힙으로 바꾸기위해 -1을 곱해서 저장
from bisect import bisect_right
import heapq, sys
input = sys.stdin.readline
n = int(input())
q = []
for _ in range(n):
deadline, benefit = map(int, input().split())
heapq.heappush(q, (-benefit, deadline))
remain = [i for i in range(1, n + 1)]
ans = 0
while q:
benefit, deadline = heapq.heappop(q)
idx = bisect_right(remain, deadline)
idx -= 1
if idx < 0:
continue
remain.pop(idx)
ans -= benefit
print(ans)
'Python > Coding Test' 카테고리의 다른 글
19235 모노미노도미노 (0) | 2022.02.13 |
---|---|
16960 스위치와 램프 (0) | 2022.02.13 |
17175 피보나치는 지겨웡~ (0) | 2022.02.10 |
15918 랭퍼든 수열쟁이야!! (0) | 2022.02.09 |
11411 합 구하기 (0) | 2022.02.09 |