알고리즘 풀이 - 백준 2109(순회강연, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

N개의 대학에서 d일 안에 강연 시 p만큼의 강의료를 지불할 때, 가장 많은 돈을 벌도록 순회강연을 하는 경우, 그 강의료의 최대값을 구하는 문제

 

 

2. 풀이

 

이 문제는 초반에 잘못 이해하여 너무 쉽게 풀고자 했다. 각 강연은 d일 안에 와서 하는 것이므로 반드시 d일에 하는 것이 아니라 1일 후 부터 d일 후 중 하루를 골라 진행하면 된다.

 

풀이 방법은 다음과 같다.

① 우선 각 강의의 정보를 저장하는 별도 Class를 생성하여 강의 정보를 저장한다.
② 강의들을 강의료를 많이 주는 순서대로 정렬한다.(즉, 강의료 기준 내림차순 정렬)
③ 강의료가 높은 강의부터 시작하여 순서대로 강의를 시작하되 해당 강의가 1일 후부터 d일 후 중 가능한 경우의 날짜라 수행하고 해당 날짜는 추가 사용하지 않는다.
  - 강의를 수행할 수 없으면(모든 날짜가 다 찼다면) 넘어간다.
④ 모든 강의에 대해 위 ③을 반복 수행한다.

 

즉, 그리디 방식으로 현재 기준 가장 강의료를 많이 주는 강의를 우선적으로 하여 각 날짜에 강의를 채워나가는 방식으로 해결하는 문제이다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static int n;
    public static void main(String[] args) throws IOException{
        // 강의 정보를 저장할 우선순위 큐를 생성하여 정렬 기준을 가격으로 내림차순 한다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Lecture> pq = new PriorityQueue<>(new Comparator<Lecture>(){
            @Override
            public int compare(Lecture o1, Lecture o2){
                if(o1.p == o2.p){
                    return o2.day - o1.day;
                }
                return o2.p - o1.p;
            }
        });

        // 각 강의를 입력받아 정보를 저장한다.
        StringTokenizer st;
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int day = Integer.parseInt(st.nextToken());
            pq.offer(new Lecture(p, day));
        }

        int ans = 0; // 수행하는 모든 강의의 강의료의 합
        
        // 우선순위 큐에서 강의 정보를 추출하여 해당 날짜부터 1일 후까지 중,
        // 비어 있는 날짜에 해당 강의를 우선으로 배정한다.
        boolean[] visited = new boolean[10001]; // 강의를 수행하는 날짜 여부
        while(!pq.isEmpty()){
            Lecture l = pq.poll();
            for(int i = l.day; i >= 1; i--){
                if(!visited[i]){
                    ans += l.p;
                    visited[i] = true;
                    break;
                }
            }
        }
        System.out.println(ans);
        br.close();
    }
}

class Lecture{
    int p;
    int day;

    public Lecture(int p, int day){
        this.p = p;
        this.day = day;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.