이번 주의 문제
https://www.acmicpc.net/problem/2109
한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.
예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.
생각해본 첫 풀이
마감일이 빠른 순으로 배치하고, 그 중에서 돈이 많은 것을 먼저 처리하면 최대가 되지 않을까?
public class 순회강연_2109 {
static class University {
int cost;
int day;
public University(int cost, int day) {
this.cost = cost;
this.day = day;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //제시하는 대학수
PriorityQueue<University> pq = new PriorityQueue<>((a, b) -> {
if(a.day == b.day) {
return b.cost - a.cost;
}
return Integer.compare(a.day, b.day);
}); //날짜 순 정렬하고 비용 높은 순으로 정렬
for(int n = 0; n < N; n++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
pq.add(new University(p, d));
}
int sum = 0;
int time = 0;
while(!pq.isEmpty()) {
University now = pq.poll();
if(now.day > time) {
time++; //하루썼으니까 뒤로 밀림
sum += now.cost;
}
}
System.out.println(sum);
}
}그러나 이런 방법으로는 3%에서 틀렸다...!!!!!!!!!!! 반례를 찾기 위해 고군분투하였으나 도저히 찾기 어려워서 백준의 질문 게시판을 방문했다.
5
3 3
2 3
1 3
100 4
90 4
맞는 답 : 195
(1,3)을 포기하고 (90, 40)를 선택하는 것이 더 최대의 이득을 볼 수 있음위의 풀이로는 여기에서 106이라는 틀린 답이 나왔다... 여기에서 제가 너무 그리디한 (탐욕적인) 방식을 생각했다는 점을 알게 되었다.
그렇다면, 날짜 순으로 우선 배치한 후, 날짜 개수 안에 해결할 수 있는 최대 금전을 매일 계산할 순 없을까?
넉넉한 날짜부터 금액 높은걸 먼저 하면 어떨까?
public class 순회강연_2109 {
static class University {
int cost;
int day;
public University(int cost, int day) {
this.cost = cost;
this.day = day;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //제시하는 대학수
PriorityQueue<University> pq = new PriorityQueue<>((a, b) -> b.day - a.day);
int max = 0;
for(int n = 0; n < N; n++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
pq.add(new University(p, d));
max = Math.max(max, d);
}
int sum = 0;
PriorityQueue<University> costPQ = new PriorityQueue<>((a, b) -> b.cost - a.cost);
for (int day = max; day >= 1; day--) {
// 현재 날짜(day) 이상 가능한 강연들만 costPQ에 추가
while (!pq.isEmpty() && pq.peek().day >= day) {
costPQ.add(pq.poll());
}
// 해당 날짜에 가장 수익 높은 강연 하나만 선택
if (!costPQ.isEmpty()) {
sum += costPQ.poll().cost;
}
}
System.out.println(sum);
}
}함께 보면 좋은 자료구조
PriorityQueue (우선순위 큐)
FIFO(First In First Out) 구조를 갖고 있는 Queue에서 우선순위(가중치)를 부여하여 정렬된 값으로 Out할 수 있도록 구현되어 있다. 삽입, 삭제에서 O(log n) 시간복잡도를 보유하고 있다.
new PriorityQueue<type>()위와 같이 구현하는데, 여기에서 type이 Integer라면 오름차순으로 (1,2,3...), String이라면 사전순으로 정렬된다. 그러나 본인이 만든 Class나 int[] 같이 여러 값이 포함되어 있는 type으로 들어가게 된다면, 따로 정렬 기준을 설정해줄 수 있다. 이 정렬 방식은 Comparator - compareTo/compare를 활용하는 방식이 있다.
compareTo 함수를 오버라이딩 하여 재정의 하면 priorityQueue 를 바로 사용할 수 있다.
public class People implements Comparable<People>{
String name;
int age;
int height;
@Override
public int compareTo(People o) {
// 키로 오름차순 정렬
// 현재 객체가 o보다 작으면 -1, 크면 1 반환
// 동일하면 0 반환
return (this.height > o.height ? 1 : -1);
}
}또는 Comparator를 통해 compare 함수를 오버라이딩 하는 방법이다.
PriorityQueue<People> pq = new PriorityQueue<>(new Comparator<People>() {
@Override
public int compare(People o1, People o2) {
return o1.height > o2.height ? 1 : -1;
}
});
하지만 이 방식보다는 나는 아래와 같은 람다 형식을 선호한다.
PriorityQueue<University> pq = new PriorityQueue<>((a, b) -> b.day - a.day); //내림차순혹시 람다에서 우선순위 기준이 여러개가 된다면, 다음과 같이 if/else를 통해 다음과 같이 표현할 수 있다.
PriorityQueue<University> pq = new PriorityQueue<>((a, b) -> {
if(a.day == b.day) {
return b.cost - a.cost;
}
return Integer.compare(a.day, b.day);
}); //날짜 순 정렬하고 비용 높은 순으로 정렬