[백준] 2109 순회강연 (JAVA)

문제 링크:

2109번: 순회강연

 

 

난이도: 골드 3

 

 

문제:

한 저명한 학자에게 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값이 주어진다.

 

 

출력:

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

 

 

문제 이해:

작성자는 처음 문제를 읽고 다음과 같은 말이 이해가 가지 않았다.

 

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

 

문제에  각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면  이 말이 핵심이다.

 

즉 1일차에 제시한 30Pay 강연을 하지 않으면 2일차엔 강연을 못하는 것이다. 

따라서 1일차에 30원 강연을 하고, 2일차에 50원 강연을 하여 결과가 80원이 나오는 것이다.

 

 

구현 방향:

작성자는 문제를 보자마자 그리디 방식을 선택하여 주어진 입력에서 1일차에서 가장 높은것, 2일차에서 가장 높은것 ... 을하여

일차별로 가장 높은 것만 선택하면 된다고 생각하여 틀렸다.

 

예를 들어 다음과 같은 입력이 있을 때,

4
2 1
3 1
4 2
5 2

정답 : 9

정답은 9가 된다.

그 이유는 2일까지 기한이 있는 강연(4, 5) 도 1일차에 수행할 수 있기 때문이다.
따라서 1일차에 4, 2일차에 5를 선택하면 총 9의 이익을 얻는다.

 

하지만 작성자가 처음 생각한 “각 날짜별 최고 강연만 선택” 방식으로는
1일차 3, 2일차 5를 선택하여 8이라는 잘못된 결과가 나온다.

 

따라서 다른 접근이 필요했고,
백준 알고리즘 분류를 참고하여 우선순위 큐(Priority Queue) 를 이용한 풀이가 적합하다는 것을 알게 되었다.

 

다음과 같이 정답을 구할 수 있다.

 

각 날짜에 가능한 강연료를 우선순위 큐(최소 힙)에 추가하고,
큐의 크기가 해당 날짜를 초과하면 가장 낮은 강연료를 제거(poll) 하는 방식으로 동작한다.
이 과정을 통해 매일 가능한 강연 중 가장 높은 강연료만을 남길 수 있다.

예를 들어, 다음과 같은 입력이 있다고 하자.

4
2 1
3 1
4 2
5 2

• 1일차:
  가능한 강연은 2, 3이다.
  → q에 [2, 3] 삽입
  → q.size() = 2 > 1 → 가장 작은 2 제거(우선 순위 큐이기에 첫 요소를 제거하면 가장 작은 요소가 제거됨)
  → q = [3]
  (1일차에는 강연료 3 선택)
• 2일차:
  가능한 강연은 4, 5이다.
  → q에 [3, 4, 5] 삽입
  → q.size() = 3 > 2 → 가장 작은 3 제거
  → q = [4, 5]
  (1일차에는 4, 2일차에는 5 선택)

마지막에 큐에 남은 값은 [4, 5],
즉, 총 강연료 = 4 + 5 = 9가 되어 최댓값이 된다.

 

작성자는 우선 가능한 일수들을 TreeSet에 저장하여 자동으로 정렬되도록 하였다.
이를 통해 날짜가 입력 순서와 관계없이 항상 오름차순으로 처리될 수 있게 했다.

 

또한, 각 날짜별로 가능한 강연료를 저장하기 위해
Map<Integer, LinkedList<Integer>> 형태의 map을 선언하였다.

이때 날짜(day)를 키(key) 로,
그 날짜에 해당하는 강연료 리스트를 값(value) 으로 두었다.

예를 들어 입력이 다음과 같을 때,

2 1
3 1
4 2
5 2

데이터는 다음과 같이 저장된다.

map key(1일차) → 2 → 3  
map key(2일차) → 4 → 5

즉, 각 날짜를 기준으로 그날까지 가능한 모든 강연료를 하나의 리스트로 관리하는 구조이다.

 

이를 그대로 코드로 구현하면 다음과 같다.

 

 

정답 코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n,p,d;
    static Queue<Integer> q=new PriorityQueue<>();
    static Map<Integer,LinkedList<Integer>> map=new HashMap<>();
    static Set<Integer> day=new TreeSet<>(); //day를 담을 set(자동 정렬)

    public static int calMoney(){
        int result=0;
        for(int calDay: day){
            for(int pay: map.get(calDay)){
                q.add(pay);
            }
            //q안에 요소가 day와 맞춰질때까지 pop
            while (q.size()>calDay){
                q.poll();
            }
        }

        //Queue안에 있는 모든 요소를 result에 합
        while (!q.isEmpty()){
            result+=q.poll();
        }
        return result;
    }
    
    public static void main(String[] args) throws IOException {
        //초기 세팅
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        n=Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            //일수와 pay를 맵에 저장
            p=Integer.parseInt(st.nextToken());
            d=Integer.parseInt(st.nextToken());

            //현재 day에 해당하는 key가 맵에 없으면 생성
            map.putIfAbsent(d,new LinkedList<>());

            //꼬리에 추가
            map.get(d).add(p);

            //set에 추가
            day.add(d);
        }

        //초기 세팅 끝

        //돈 구하기
        int result = calMoney();

        //결과 출력
        System.out.println(result);


    }
}

 

 

마무리하며:

처음에는 단순히 그리디하게 큰 값만 선택하면 되겠지 라는 생각으로 접근했지만,
문제를 풀면서 그 방식이 모든 경우를 커버하지 못한다는 것을 알게 되었다.

 

특히 “마감일이 더 긴 강연도 앞날에 수행할 수 있다”는 점이 핵심이었고,
이 부분을 처리하기 위해 단순 정렬만으로는 부족했다.

 

그 과정에서 우선순위 큐(PriorityQueue) 라는 자료구조를 처음 접하게 되었고,
이를 이용하면 매 순간 가장 작은 값을 빠르게 제거하면서
자연스럽게 최적의 강연 조합을 만들 수 있다는 점에서 우선순위 큐에 강점을 알게 되었다.

 

 

감사합니다.