기술 블로그

1781번 컵라면 본문

알고리즘 문제/BOJ

1781번 컵라면

parkit 2019. 12. 23. 22:20
728x90
반응형

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<intint> > 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<intint> > 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














728x90
반응형

'알고리즘 문제 > 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