일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 처우협의
- 물채우기
- softeer
- 처우산정
- 퇴사통보
- @P0
- 성적평가
- 매개변수탐색
- 경력
- compose
- Docker
- Kafka
- msSQL
- boj #19237 #어른 상어
- BOJ
- upper_bound
- 13908
- 이분탐색
- BFS
- incr
- OFFSET
- 오퍼레터
- 소프티어
- 기술면접
- dfs
- 연결요소
- 파라메트릭
- 6987
- 백트래킹
- 백준
- Today
- Total
기술 블로그
1781번 컵라면 본문
https://www.acmicpc.net/problem/1781
priority_queue를 활용한 Greedy 문제이다.
제일 먼저 정렬을 한다.(데드라인이 제일 중요하므로 우선 그 다음 컵라면의 개수)
알고리즘 진행 동안 데드라인과 priority_queue의 size()를 잘 비교해야한다.
현재 데드라인이 priority_queue의 size()보다 크거나 같으면,('='일 때는 데드라인과 priority_queue의 size()가 같을 수도 있으니)
priority_queue에 마이너스 상태로 넣어준다.(최소 힙으로 만들기 위함 그리고 데드라인보다 작으므로 '더' 진행할 수 있으니 push)
그리고 데드라인이 priority_queue의 size()보다 작으면 priority_queue를 pop() 해줘야 한다.(데드라인을 초과할 수는 없으므로)
pop()을 할 때에는 쓸모없는 것들이 없어진다.
즉, 현재 데드라인을 고려하여 priority_queue 안에는 항상 적절한(정답을 구하기 위한) 컵라면의 개수들이 담겨져 있다.
한 가지로 예를 보자
3
1 2
1 10
3 1
정렬을 하면,
1 2
1 10
3 1
이 된다.
[1, 2]
데드라인 = 1, 컵라면의 개수 = 2, pq.size() = 0
데드라인이 pq.size() 이상이므로, pq.push(-2)를 해준다.
pq의 현재 상태 = [-2](맨 왼 쪽이 꼭대기)
[1, 10]
데드라인 = 1, 컵라면의 개수 = 10, pq.size() = 1
데드라인이 pq.size() 이상이므로, pq.push(-10)를 해준다. → 이 때문에 >=를 해준 것이다. 더 좋은 답을 위한 데이터가 나올 수 있으니.
pq의 현재 상태 = [-2, -10](맨 왼 쪽이 꼭대기)
30번 째 줄에서
데드라인(1) < pq.size()(2) 이므로, pq.pop()을 해줘야 한다. → < 인 이유는 <=로 한다면, pq.size()가 더 작아질 수 있다.
pq의 현재 상태 = [-10](맨 왼 쪽이 꼭대기)
.
.
.
이런 식으로 진행된다.
++)
사실 접근 방법은 결국 "절대로 선택될 수 없는 컵라면"들은 제외하면서 접근해도 된다.
예를 들어
데드라인 컵라면 개수
10 1
10 2
10 3
.
.
앞에 1, 2, 3, .. 개수가 적은 것들은 선택될 수 없다.
그러므로, 우선순위 큐(최소 힙)에 우선 push를 하면서 진행하다가,
해당 i번 째에 대해서 데드라인의 수와 우선순위 큐(최소 힙)의 size()가 같게 만들도록 하면 된다.
(또는 우선순위 큐의 size()가 더 적게)
그러면 위에서 적은 것들부터 데드라인의 개수에 맞게 구할 수 있다.
어차피 정렬하였으므로 데드라인은 증가할 것이고, 최대 데드라인에 맞춰야 하기 때문이다.
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 42 43 44 45 | #include <bits/stdc++.h> using namespace std; int n; vector<pair<int, int> > v; int main() { //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin); cin.tie(0); scanf("%d", &n); int deadline, cup_count, ans = 0; for (int i = 0; i < n; i++) { scanf("%d %d", &deadline, &cup_count); v.push_back({ deadline, cup_count }); } sort(v.begin(), v.end()); priority_queue<int> pq; for (auto i : v) { int dl = i.first, cc = i.second; if (dl >= pq.size()) { pq.push(-cc); } while (dl < pq.size()) { pq.pop(); } } while (!pq.empty()) { ans += -pq.top(); pq.pop(); } printf("%d\n", ans); return 0; } | cs |
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 42 43 44 | #include <bits/stdc++.h> using namespace std; int n; priority_queue<int> pq; vector<pair<int, int> > v; int main() { cin.tie(0); scanf("%d", &n); int deadline, cup; for (int i = 0; i < n; i++) { scanf("%d %d", &deadline, &cup); v.push_back({ deadline, cup }); } sort(v.begin(), v.end()); for (int i = 0; i < n; i++) { int dl = v[i].first, cp = v[i].second; pq.push(-cp); while (dl < pq.size()) { pq.pop(); } } int answer = 0; while (!pq.empty()) { answer += -pq.top(); pq.pop(); } printf("%d\n", answer); return 0; } | cs |
'알고리즘 문제 > BOJ' 카테고리의 다른 글
14927번 전구 끄기 (0) | 2019.12.25 |
---|---|
1080번 행렬 (0) | 2019.12.24 |
1138번 한 줄로 서기 (0) | 2019.12.21 |
2631번 줄세우기 (0) | 2019.12.17 |
1300번 K번째 수 (0) | 2019.12.17 |