BOJ 2109 순회 강연

한 학자에게 대학들에서 강연 요청이 들어왔는데, 각 대학마다 며칠 안에 와서 강의 해주면 얼마만큼의 강연료를 지불하겠다는 조건이 주어진다. 그 학자는 하루에 한 곳에서만 강연을 할 수 있다고 할 때, 적절하게 강연할 대학을 선택해서 최대로 벌 수 있는 돈을 구하는 문제이다.

확실치는 않지만... 왠지.. greedy 같아 보인다.
일단 강연료 기준으로 내림차순으로 정렬을 하고 보면서... 가장 강연료가 큰 강의부터 선택해 나가면 될 것 같다. 어떤 강의를 하든 하루에 하나의 강의만 해야할 것이고 결국 어떤 날에 강의를 할 것이라면 강의료가 가장 큰 강의를 하는 것이 돈을 최대로 벌 수 있는 방법이라는 생각이 들었다.

그렇다면 이제 문제는 어떤 날에 어떤 강의를 할 것이냐인데, 강연료가 큰 순으로 한다고 해도 하루에 하나밖에 할 수 없고, 강연을 할 수 있는 기한은 정해져있고 서로 다르므로 어떤 강연은 자신보다 강연료가 큰 강연때문에 못하고 넘어갈 수도 있는 것이다.
이렇게 생각하다보니 그럼 강연료가 큰 순으로 보되, 각각 어디에 배치시킬 건지 다 해봐야할 것 같고 그러기 위해서는 dp를 이용해야 하는건가...라는 생각이 들었다..  음 근데 메모리 초과가 날 것 같아서... 좀 더 생각해보기로 했다.

좀 더 생각해보니 여기서 주어지는 일수는 강연 요청이 들어왔을 때부터 시작하는.. 즉 모든 대학에서 첫째날부터 시작해서 동시에 흘러가는 시간 즉 공유되는, 겹치는 부분이 있는 시간이므로 공통인 날의 개수는 첫째날이 제일 많고 그 다음 둘째날... 이런 식이다. 내가 좀 말을 어렵게 했는데 결론은 강연료가 큰 순으로 보면서 날짜를 선택할 때 가능한 날짜 중 마지막에 가까운 날짜부터 선택을 해 나가야 한다는 것이다. 왜냐하면 첫째날에 가까운 날짜일수록 다른 강연과 겹치는 경우가 많아지기 때문에 가능한 날짜 중 마지막에 가까운 날짜부터 선택해 나가야 그 다음 강연을 선택할 때 강연료가 큰 강연을 최대한 많이 선택할 수 있을 것이다.

결국 greedy algorithm인가... 내가 생각해서 쓰긴 했지만 뭔가 확실하게 와닿지는 않는다. 아직도 살짝 헷갈리기도 하고... 일단 풀어서 제출해 봐야겠다. 그리고 주말에 백준님 풀이도 귀담아 들어봐야겠다.

코드를 짜보니 강연료가 큰 순으로 보면서 각 강연마다 주어진 마지막 날짜부터 가능한 날짜를 봐야하므로 O(n제곱)이 걸릴 것 같다.
제출해서 AC를 받았다. 그런데 시간이 좀 걸리는 편이다. 다른 사람들 코드 구경 좀 해야겠다.