문제 링크입니다: https://www.acmicpc.net/problem/1781
1781번: 컵라면
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다. 문제 번호 1 2 3 4 5 6 7 데드라인 1 1 3 3 2 2 6 컵라면 수 6 7 2 1 4 5 1 위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을
www.acmicpc.net
그리디하게 접근해야하는 문제였습니다.
접근법은 아래와 같습니다.
1. 데드라인을 1순위로, 컵라면 수를 2순위로 정렬을 해줍니다.
2. 데드라인이 긴 순서부터 최대 힙에 컵라면 수를 넣어주고 각 초마다 힙의 top을 결과에 더해나가면 됩니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1712번 손익분기점 (3) | 2019.11.10 |
|---|---|
| 백준 12018번 Yonsei TOTO (0) | 2019.11.09 |
| 백준 2262번 토너먼트 만들기 (0) | 2019.11.08 |
| 백준 1911번 흙길 보수하기 (0) | 2019.11.08 |
| 백준 2212번 센서 (0) | 2019.11.08 |