반응형 그리디 알고리즘1 백준 2109 처음에는 우선순위 큐를 사용해서 비용이 크고 기간이 짧은 강연을 먼저 고르면 될 줄 알았다. 그런데 4 5 1 10 2 20 2 10 3 이러한 예시가 들어올 경우 5 + 2 + 10 이 아니라 10 + 20 + 10 을 선택해야 했다. 왜냐하면 기간 내에 강연을 가는 것도 가능하기 때문이다. 그래서 아예 새로운 방법을 사용해야 했다. 1. 최대 기간 maxDate 잡기 2. 비용이 큰 순서대로 입력값 정렬하기 3. maxDate에서 하루씩 줄여가며 가능한 강연 찾기 위 예시에서는 maxDate = 3 이 될 것이다. 비용이 큰 순서대로 입력값을 정렬하면 [[20, 2], [10, 2], [10, 3], [5, 1]] 이 될 것이다. 그러면 3에서 부터 2, 1 와 같이 1씩 줄여가면서 해당 날짜에 가능.. 2021. 5. 2. 이전 1 다음 반응형