문제 링크입니다: 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을 결과에 더해나가면 됩니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <queue> | |
#include <algorithm> | |
using namespace std; | |
int main(void) | |
{ | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
int N; | |
cin >> N; | |
vector<pair<int, int>> v(N); | |
for (int i = 0; i < N; i++) | |
{ | |
cin >> v[i].first >> v[i].second; | |
--v[i].first; | |
} | |
sort(v.begin(), v.end()); | |
int result = 0; | |
int idx = N - 1; | |
priority_queue<int> pq; | |
// 데드라인이 높은 순서 | |
for (int i = N - 1; i >= 0; i--) | |
{ | |
for (; idx >= 0 && v[idx].first == i; idx--) | |
{ | |
pq.push(v[idx].second); | |
} | |
// maxHeap | |
if (!pq.empty()) | |
{ | |
result += pq.top(); | |
pq.pop(); | |
} | |
} | |
cout << result << "\n"; | |
return 0; | |
} |


개발환경: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 |