[백준 15590] Rental Service
문제 www.acmicpc.net/problem/15590 알고리즘 greedy 풀이 $N$마리의 소, $M$명의 우유 구매자, $R$명의 대여 희망자가 주어질 때, 얻을 수 있는 최대 수익을 구하는 문제입니다. 소를 우유 생산량에 따라 정렬해놨을 때, $i$번 소까지는 대여를 하고, 그 이후의 소들은 젖을 짜 우유를 판매하는 것이 최적이므로 우리는 어느 소까지만 대여를 해줄지 구해야합니다. 일단 모든 소를 대여해준 후 가장 가치가 높은 소(우유 생산량이 가장 많은 소)부터 우유를 짜서 가장 비싸게 사는 사람에게 판매합니다. 대여 희망자에 대한 누적합을 구해놓았다면 $i$번째 사람까지 대여를 했을 때 벌 수 있는 돈을 $O(1)$에 구할 수 있습니다. 이때 정답이 더 크게 갱신이 된다면 계속 진행을 하고..
Algorithm
2021. 1. 26. 13:39
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- dfs
- 이분매칭
- Fenwick
- Suffix Array
- greedy
- kmp
- Segment tree
- 정렬
- dijkstra
- Oracle
- bfs
- union find
- 동적계획법
- 트라이
- 좌표압축
- sweeping
- 2-SAT
- sorting
- spring boot
- 펜윅트리
- 이분탐색
- knapsack
- 세그먼트트리
- spring
- 스위핑
- string
- hld
- implementation
- SCC
- DP
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함