[백준] 2109번 순회강연 Java

문제 링크

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만큼의 돈을 벌 수 있다.

풀이

1. 먼저 강연료가 높은 순으로 정렬해준다.

2. for 문을 돌리면서 나온 값 순서대로 스케줄을 확인하는데 강연은 기한을 최대한 지키는 선에서 스케줄에 넣어준다.
   ex) d가 10이면 10일 안에 강연해야 하기에 최대한 기한을 지키는 선 10에서부터 -1을 하면서 스케줄 표를 확인하고 없는 날짜에 넣어줌.

3. 스케줄에 들어갔다면 강연료를 ans에 더해준다.

4. for 문이 끝났다면 ans 값은 최댓값이 된다.

소스 코드

import java.io.*;
import java.util.*;

class Lecture implements Comparable<Lecture> {
    int p,d;
    public Lecture(int p, int d) {
        this.p = p;
        this.d = d;
    }
    
    @Override
    public int compareTo(Lecture l) {
        int dif = l.p - this.p;
        if(dif>0) return 1;
        if(dif<0) return -1;
        return 0;
    }
}

public class Main {
    static int N;
    static int ans = 0;
    static boolean schedule[] = new boolean[10001];
    static Lecture lec[];
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        lec = new Lecture[N];
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int lp = Integer.parseInt(st.nextToken());
            int ld = Integer.parseInt(st.nextToken());
            lec[i] = new Lecture(lp, ld);
        }
        Arrays.sort(lec);
        for(int i=0; i<N; i++) {
            if(find_schedule(lec[i].d)) {
                ans += lec[i].p;
            }
        }
        System.out.println(ans);
    }
    
    static boolean find_schedule(int s) {
        for(int i=s; i>=1; i--) {
            if(!schedule[i]) {
                schedule[i] = true;
                return true;
            }
        }
        return false;
    }
}