백준 13904. 과제

https://www.acmicpc.net/problem/13904

13904번: 과제

 

이 문제는 그리디하게 풀수도 있고, 우선순위큐를 이용할수도 있다.

 

그리디 

그리디 하게 생각해보면, 점수가 높은 문제를 최대한 늦게 수행하면 될것이다.

mark[i] = j (i일에 j점 과제를 수행함) 배열을 만들어서 과제 수행일 이내에서 최대한 늦게 수행하도록 한다.

 

 

 

 

우선순위 큐

우선순위 큐를 이용하는 방법은 마감일이 빠른 과제부터 수행한다.

그러다가 마감일이 지난 과제를 만나면 현재까지 수행한 과제중 가장 점수가 낮은 과제를 빼주면 된다.