그리디 알고리즘 문제이다.
예를 들어
4
10 4
20 2
30 2
40 1
이러한 예제가 있다고 해보자
먼저 강의 가격순으로 배열이 정렬된다.
40 1
30 2
20 2
10 4
그 후 가격이 큰 순서대로 탐색하며 그 강의의 날짜 기한을 살펴본다.
값이 40인 강의의 기한은 1일이므로 날짜 배열의 1 즉, day[1]
을 살펴본다. 비어있으므로 40 강의를 넣고 정답에 더해준다.
그 다음으로 30 인 강의도 day[2]
에 넣어주고 가격을 더해준다.
그 다음 20인 강의도 날짜 배열을 살펴본다. day[2]
를 살펴보고 그 전날인 day[1]
도 살펴 봤지만 들어갈 공간이 없으므로 저 강의는 진행하지 못한다. 패쓰
마지막으로 10인 강의를 탐색한다. 날짜 배열 day[4]
는 비어있으므로 대입하고 정답에 더해준다.
결국엔 답이 80이 된다.
public class bj2109 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
lecture[] lectures = new lecture[N];
int lastDay = -1;
for (int i = 0; i < N; i++) {
String line = br.readLine();
String[] split1 = line.split(" ");
lectures[i] = new lecture(Integer.parseInt(split1[0]), Integer.parseInt(split1[1]));
lastDay = Math.max(lastDay, lectures[i].day);
}
// 페이가 쎈 것부터 확인
Arrays.sort(lectures, (o1, o2) -> o2.pay - o1.pay);
boolean[] day = new boolean[lastDay + 1];
long answer = 0;
for (lecture l : lectures) {
int d = l.day;
while (d > 0) {
if (!day[d]) {
answer += l.pay;
day[d] = true;
break;
}
--d;
}
}
System.out.println(answer);
br.close();
}
public static class lecture {
int pay;
int day;
public lecture(int pay, int day) {
this.pay = pay;
this.day = day;
}
}
}