BOJ 13904 과제

하루에 하나의 과제를 끝낼 수 있고, 각 과제마다 마감일까지 남은 일수가 주어진다. 마감일을 넘으면 과제에 대한 점수를 못받는다. 이 때, 받을 수 있는 점수의 최대값을 구하는 문제인데, 어디서 많이 본듯한 그리디 문제이다.

점수를 최대한으로 받으려면, 점수가 큰 과제를 우선적으로 하거나 많은 과제를 해야 한다.
여기서 마감일이 주어지는데, 일단 점수가 크든 작든 마감일이 많이 남은 과제는 나중에 생각해도..   일단 하루에 한 과제씩 할 수 있으므로 주어진 최대 마감일까지 하루에 한 과제씩 꼭 해야한다. 그리고 한 과제씩 하되 점수가 큰 과제를 해야한다.
그리고 마감일이 주어지면 어떤 과제든 마감일 안에 아무때나 해도 점수는 같기 때문에 마감일이 길면 마감일이 짧은 작업에 양보해주고 그 작업은 나중에 하는 것이 좋다.

그렇지만 마감일이 짧은 작업을 먼저 하느라 더 큰 과제를 놓치면 안되기 때문에 점수 순으로 정렬을 해서 점수가 큰 과제부터 본다.
그리고 어차피 하루에 한 과제가 최대이기 때문에 이왕 하는 거 점수가 큰 과제를 하는 것이 이익이다. 그리고 점수가 큰 과제부터 하되, 그 과제의 마감 기한의 마지막 날에 해야 마감일이 짧은 작업들을 최대한 많이 할 수 있다.

그래서 점수가 큰 과제부터 하되, 마감 기한의 마지막 날에 배정하면서 점수를 계산하면 될 것이다.

BOJ 2109 순회 강연 문제와 비슷한 문제이길래 내가 블로그에 정리해놓은 것을 봤는데,
다시 정리해보면 어떤 날에 과제를 할 것이라면 가장 큰 점수의 과제를 하는 것이 좋고, 앞의 날들일수록 과제들끼리 공유되는 부분이 크므로(즉, 가능한 과제의 경우가 많으므로) 그 과제의 기한의 마지막 날에 하는 것이 가장 좋은 방법이다. 그리고 만약 가장 큰 점수의 과제 대신 작은 점수의 과제를 한다고 해서 이익이될 것이 없다. 왜냐하면 그날 할 수 있는 과제는 어차피 1개이고, 그날 과제를 함으로써 영향이 발생하는 것은 그날이 기한 안에 있는 과제들을 못하게 된다는 것인데, 앞서 말했듯이 그 날 하나의 과제를 할 것이라면 가장 큰 점수를 하는 것이 이익이므로 가장 큰 점수의 과제를 그 과제의 기한의 끝에 하는 것이 가장 큰 점수를 얻는 방법이 될 것이다.