티스토리 뷰
문제
https://www.acmicpc.net/problem/9869
알고리즘
Greedy
풀이
소마다 우유생산량과 수명이 주어질 때, 최대 우유생산량을 구하는 문제입니다.
자주 보이는 그리디 테크닉입니다. 시간을 0부터 접근하는 대신, 가장 마지막 시간부터 0까지 역순으로 소들을 고려합니다. T에 해당하는 시간에 젖을 짤 수 있는 소들을 PQ에 넣습니다. 이렇게 하면 현재 젖을 짤 수 있는 소들이 PQ에 담기게 됩니다. 이 가운데 우유 생산량이 높은 소부터 젖을 짜나가면 됩니다.
코드
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
int N, T, ans;
bool used[MAXN + 5];
int main() {
#ifndef ONLINE_JUDGE
freopen("3.in", "r", stdin);
freopen("out", "w", stdout);
#endif
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> N;
vector<pii> vt;
rep(i, N) {
int gal, dead;
cin >> gal >> dead;
T = max(T, dead);
vt.emplace_back(gal, dead);
}
priority_queue<pii> pq;
sort(vt.begin(), vt.end(), [](const pii& a, const pii& b) {
return a.second > b.second;
});
int i = 0;
while (T) {
for (; i < N;) {
if (vt[i].second == T) pq.emplace(vt[i++]);
else
break;
}
if (!pq.empty()) {
ans += pq.top().first;
pq.pop();
}
--T;
}
cout << ans;
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준 17612] 쇼핑몰 (0) | 2021.05.28 |
---|---|
[백준 10652] Piggy Back (0) | 2021.05.27 |
[백준 18785] Clock Tree (0) | 2021.05.16 |
[백준 20970] Dance Mooves (0) | 2021.05.15 |
[백준 20649] Stuck in a Rut (0) | 2021.05.14 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- knapsack
- Fenwick
- Oracle
- 펜윅트리
- Segment tree
- 동적계획법
- 2-SAT
- Suffix Array
- greedy
- implementation
- DP
- bfs
- dijkstra
- 정렬
- 스위핑
- kmp
- sorting
- sweeping
- SCC
- 세그먼트트리
- string
- dfs
- union find
- hld
- spring boot
- 좌표압축
- 이분매칭
- 트라이
- spring
- 이분탐색
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함