[Algorithm] BOJ_13904 과제 C#

---

문제

---

입력 출력

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.
다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제

---

예제 입력 1

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

예제 출력 1

185

---

풀이 및 코드

 public class Boj13904
    {
        static void Main(String[] args)
        {

            int n = Convert.ToInt32(Console.ReadLine());

            Homework[] works = new Homework[n];

            for (int i = 0; i < n; i++)
            {
                String[] strArr = Console.ReadLine().Split();
                works[i] = new Homework(Convert.ToInt32(strArr[0]), Convert.ToInt32(strArr[1]));
            }

            works = works.OrderByDescending(i => i.deadline).ToArray();
            int idx = 0, result = 0;
            
            // 우선순위 큐 : 큐에서 우선 순위가 가장 낮은 항목이 제거된다.
            PriorityQueue<Homework, int> queue = new PriorityQueue<Homework, int>();

            for (int i = 100; i > 0; i--)
            {
                // 인덱스가 개수 n 을넘어가지 않으면서 데드라인이 i일보다 큰 데드라인만 큐에 넣는다.
                while (idx<n && works[idx].deadline>=i)
                {
                    // 큐에 집어넣고 배열의 인덱스를 증가시킨다.
                    queue.Enqueue(works[idx], -works[idx++].score); 
                }

                // 우선순위 큐에 담긴 갯수가 1개라도 있으면 결과값에 누적합을 한다.
                if (queue.Count > 0)
                {
                    result += queue.Dequeue().score; // 우선순위가 낮은 항목부터 나옴
                }
            }

            Console.WriteLine(result);

        }
    }

    public class Homework
    {
        public int  deadline { get; set; }
        public int  score { get; set; }

        public Homework()
        {
        }

        public Homework(int deadline, int score)
        {
            this.deadline = deadline;
            this.score = score;
        }
    }

---

출처

https://www.acmicpc.net/source/52179515