반응형
https://www.acmicpc.net/problem/1781
1781번: 컵라면
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라
www.acmicpc.net
[ 문제풀이 ]
1. 데드라인과 컵라면 개수를 입력받고 arr 배열에 저장합니다.
2. arr배열을 데드라인을 기준으로 오름차순으로 정렬합니다.
3. 1부터 N까지 for문을 통해 돌면서 priority_queue에 넣어주고, arr[ i ]의 데드라인보다 pq.size()가 크면 pq.pop()을 해줍니다.
4. pq에 있는 모든 값을 더하고, 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; int N; int ans; int main() { priority_queue<int, vector<int>, greater<int>> pq; vector<pair<int, int>> arr; scanf("%d", &N); for (int i = 0; i < N; i++) { int a, b; scanf("%d %d", &a, &b); arr.push_back({ a,b }); } sort(arr.begin(), arr.end()); for (int i = 0; i < N; i++) { pq.push(arr[i].second); if (arr[i].first < pq.size()) { pq.pop(); } } while (!pq.empty()) { ans += pq.top(); pq.pop(); } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 14921번 - 용액 합성하기 (C++) (0) | 2023.03.29 |
|---|---|
| [ 백준 ] 11265번 - 끝나지 않는 파티 (C++) (0) | 2023.03.28 |
| [ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++) (0) | 2023.03.26 |
| [ 백준 ] 23286번 - 허들 넘기 (C++) (0) | 2023.03.25 |
| [ 백준 ] 15422번 - Bumped! (C++) (0) | 2023.03.24 |