[백준][알고리즘]순회강연-2109
문제출처 : 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만큼의 돈을 벌 수 있다.
입력
첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.
출력
첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
풀이
-> 해당 문제는 탐욕 알고리즘을 이용하여 풀이가 가능합니다.
1) 입력받은 강연료를 기준으로 내림차순으로 정렬을 하여 강연료가 큰 순서로 정렬해 줍니다.
2) 정렬된 데이터를 기준으로 강연료가 큰 방문일에 대해 방문 가능 여부를 체크하며 총 페이를 계산해준다.
여기서 많이들 헷갈리는 상황이 발생한다.
하루에 한곳만 방문을 하는 것은 맞으나 주어진 방문일은 꼭 그 날에 방문을 해야한다는 말이 아니다.
예를들어 아래와같이 3개의 데이터가 주어진 상황이다.
|
idx
|
강연료
|
방문일
|
|
0
|
1
|
1
|
|
1
|
10
|
2
|
|
2
|
10
|
2
|
이 때 보통 헷갈리는 부분이 1일차에는 idx=0인 강연료 1과 2일차는 idx=1or 2인 것을 골라 답으로 11로 제출하는상황이 발생한다.
하지만 주어진 문제에서는 방문일 기간안에만 방문하면 된다는 의미이다. 위의 예시에 데이터 기준으로 강연료가 가장 큰 idx=1,2를 보면 모두 2일안에만 방문하면 된다는 이야기이다. idx=1을 선택하고 나서 다시 idx =2를 선택해도 두 선택지 모두 2일안에 방문하는 조건을 만족하게 되는 것이다. 그래서 위와 같은 예시의 정답은 20이 되게 된다.
이 문제의 반례사례를 보면 위와 같이 착각하는 경우가 대다수이다.
public class Greedy2109Alpha {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken());
ArrayList<Lecture> list = new ArrayList<>();
for(int i=0; i< cnt;i++) {
st = new StringTokenizer(br.readLine());
int pay = Integer.parseInt(st.nextToken());
int day = Integer.parseInt(st.nextToken());
list.add(new Lecture(pay, day));
}
Collections.sort(list, Collections.reverseOrder()); //(list);
boolean[] check = new boolean[10001];
int resMoney = 0;
for(int i=0; i<list.size();i++) {
// 위의 2번 풀이에 대한 부분
for(int j = list.get(i).day ; j>=1; j-- ) {
if(!check[j]== true ) {
resMoney = resMoney + list.get(i).pay;
check[j] = true;
break;
}
}
}
System.out.println(resMoney);
}
static class Lecture implements Comparable<Lecture>{
int day;
int pay;
public Lecture(int pay, int day) {
this.day = day;
this.pay = pay;
}
@Override
public int compareTo(Lecture o) {
return this.pay -o.pay;
}
}
}