알고리즘/BOJ

백준 1781번 컵라면

꾸준함. 2019. 11. 9. 00:51

문제 링크입니다: 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을 결과에 더해나가면 됩니다.

 

#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;
}
view raw .cpp hosted with ❤ by GitHub

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