[Inflearn] 최대 수입 스케쥴(priority_queue 응용)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - D일 안에 와서 강연을 해 주면 M 만큼의 강연료

     - D와 M을 바탕으로 가장 많이 돈을 벌 수 있도록 스케쥴을 짜야 함

     - 강연은 하루에 하나의 강연

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

6

50 2 

20 1 

40 2 

60 3 

30 3 

30 1

이 입력으로 주어졌을 때,

먼저 요청날짜를 기준으로 최대힙을 만들면

대략적으로

60 3

30 3 

50 2

40 2

30 1

20 1

이렇게 트리가 구성될 것이다.

여기서 수강료가 큰 순서대로의 합을 구하면 된다.

최대 요청 날짜가 3일 이므로, 

가장 큰 순서 대로 수강료를 나열했을 때,

60 + 50 + 40 = 150 이 정답이 된다. 

이 방법은 우선순위 큐에 수강료를 쌓은 후 가장 높은 수강료를 뽑는 방식과 비슷하다.

#. Code

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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include <cstdio> #include <vector> #include <queue> #include <algorithm>   using namespace std;   struct lecture {     int money;     int day; };   bool compare(const lecture &a, const lecture &b) {     if (a.day == b.day)         return a.money > b.money;          return a.day > b.day; }   int main(void) {     freopen("input.txt", "rt", stdin);       int n, i, a, b, income = 0, rest = 0;     vector<lecture> vt;     priority_queue <int> pQ;       scanf("%d", &n);       for (i = 0; i < n; i++)     {         scanf("%d %d", &a, &b);           vt.push_back({ a, b });     }       sort(vt.begin(), vt.end(), compare);       rest = vt[0].day;       i = 0;     while (rest)     {         while (true)         {             if (i < n && vt[i].day == rest)                 pQ.push(vt[i++].money);             else                 break;         }                  rest--;           if (pQ.empty())             continue;           income += pQ.top();         pQ.pop();     }       printf("%d\n", income);       return 0; } Colored by Color Scripter

cs

우와아아아악 계속 메모리 접근 에러가 떠서 디버깅만 엄청 한 것 같다.

첫 번째 문제는 sort() 에서 end() 를 사용하지 않고, 마지막 index 를 참조하다보니까 정렬도 덜 되었었고,

line 48 에서 i 가 index 를 초과해버려서 문제가 생겼었다.

또 line 59 에서도 비어있는 queue 를 참조하니 문제가 있었었다.

문제 투성이구만ㅋㅋㅋ

차근차근 잘 생각하면서 해야겠다ㅠㅠ

너무 빨리 풀려고만 하다보니 생각이 짧아지는 것 같다..

로직은 이렇다

line 36) 입력받은 수강료와 요청 날짜를 구조체로 묶어서 vector 에 저장한다.

line 39) vector 에 저장된 수강료, 요청 날짜 쌍을 요청 날짜가 큰 순서(일정이 많이 남은 강의)로 정렬한다.

          두 번째 정보(남은 일수)를 기준으로 정렬하기 위하여 line 14~20) 에 compare 함수를 만들어야 했다. 

line 44) 모든 요청 일수를 참조할 것이다.

line 48~52) 해당 일수의 강의 수강료를 priority_queue 에 push

line 54) 해당 일수에 해당하는 강의를 모두 탐색하였으므로 -- 해준다.

line 56~57) priority_queue 가 비어있다면 continue;

line 59~60) priority_queue 에 있는 가장 높은 수강료를 참조해서 수입에 더해주고 가장 높은 수강료를 pop 해준다.

ㅇ코드 다듬기

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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

#include <cstdio> #include <vector> #include <queue> #include <algorithm>   using namespace std;   struct Lecture {     int money;     int day;     Lecture(int a, int b)     {         money = a;         day = b;     }     bool operator<(const Lecture& b) const     {         return day > b.day;     }   };   int main(void) {     freopen("input.txt", "rt", stdin);       int n, i, j, a, b, income = 0, rest = 0;     vector<Lecture> vt;     priority_queue <int> pQ;       scanf("%d", &n);       for (i = 0; i < n; i++)     {         scanf("%d %d", &a, &b);           vt.push_back(Lecture(a, b));     }       sort(vt.begin(), vt.end());       rest = vt[0].day;     j = 0;     for (i = rest; i >= 1; i--)     {         for (; j < n; j++)         {             if (vt[j].day < i)                 break;               pQ.push(vt[j].money);         }           if (!pQ.empty())         {             income += pQ.top();             pQ.pop();         }     }       printf("%d\n", income);       return 0; } Colored by Color Scripter

cs

#. Other code

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 46 47 48

#include<stdio.h> #include<algorithm> #include<queue> #include<vector> using namespace std;   struct Data{     int money;     int when;     Data(int a, int b){         money=a;         when=b;     }     bool operator<(const Data &b)const{         return when>b.when;     }     };   int main(){     int n, i, j, a, b, res=0, max=-2147000000;         vector<Data> T;     priority_queue<int> pQ;       scanf("%d", &n);     for(i=1; i<=n; i++){         scanf("%d %d", &a, &b);         T.push_back(Data(a, b));         if(b>max)             max=b;     }       sort(T.begin(), T.end());         j=0;       for(i=max; i>=1; i--){             for( ; j<n; j++){             if(T[j].when<i) break;                         pQ.push(T[j].money);         }         if(!pQ.empty()){             res+=pQ.top();             pQ.pop();         }     }       printf("%d\n",res);     return 0; } Colored by Color Scripter

cs

이 코드를 보니.. 아직도 나는 주먹구구식으로 짜고 있었다는 것을 느낀다..

line 7~17) 수강료와 기한을 저장할 구조체를 생성한다. 

line 10~13) 매개변수가 있는 생성자 선언

line 14~16) sort() 함수를 구조체의 when 기준 내림차순으로 적용하기 위해 선언

line 25~30) 수강료와 기한을 입력받고, 구조체를 담는 벡터에 push() 해준다.

line 28~29) 가장 긴 기한을 max 변수에 저장한다.

line 32) 구조체를 담은 벡터를 정렬하는데 line 14 에 선언한 operator 함수에 의해 when 기준 내림차순으로 정렬이 된다.

line 35~44) 가장 긴 기한을 기준으로 줄여가면서 각 기간의 수강료를 탐색한다.

line 36~39) 특정 기한보다 크거나 같다면 priority queue 에 넣어준다.

line 40~43) priority queue 가 비어있지 않다면 pQ에 있는 가장 큰 수강료를 결과에 더해준 후 pop() 해준다.

내 코드에 대한 반성을 하자면..

전체적인 로직은 비슷하나

구조체를 만들고 생성자도 없고 compare 함수도 operator 로 단순하게 구현할 수 있었는데 복잡하게 한 것 같다.

line 48~51 부분도 조건을 복잡시럽게 해놓고,

line 56~57 부분도 굳이 필요 없고, not 일 경우 아래 동작들을 수행하게 하면 되었는데, 코드를 다듬는 작업이 필요한 것 같다..

#. Result

  - Input --------------------------------------------------------

6 

50 2 

20 1 

40 2 

60 3 

30 3 

30 1

------------------------------------------------------------------

  - Output --------------------------------------------------------

150

------------------------------------------------------------------