[백준] 2109번 순회강연 문제 풀이 : Programming Story

1. 문제

www.acmicpc.net/problem/2109

문제는 위의 백준 링크에 들어가보면 볼 수 있다.

이 문제는 전 포스팅에서 다루었던,

https://www.programmingstory.com/2024/03/1202-priorityqueue.html

보석도둑 문제와 굉장히 유사한 문제라고 할 수 있다. 유사한 풀이로 이 문제도 풀어볼 것이니 위의 포스팅이 큰 도움이 될 것이다.

2. 풀이

이 문제는 예를 들어서 4일 차에는 강연을 4일내, 5일내, 6일내...등등으로 부탁한 강의들만 할 수 있기 때문에 강의를 day를 기준으로 내림차순으로 정렬하는 것이 필요하다.

그래서, Lecture class를 하나 생성해주고,

class Lecture implements Comparable<Lecture>{
    int price, day;
    Lecture(int price, int day){
        this.price=price;
        this.day=day;
    }
    public int compareTo(Lecture a){
        if (a.day!=this.day){
            return a.day-this.day;
        }
        else{
            return a.price-this.price;
        }
    }
}

코드를 위와 같이 적어주었다. day를 기준으로 내림차순으로 정렬할 수 있도록 compareTo method를 구현해주었다.

이렇게 class를 만들어 준 뒤에는 PriorityQueue를 사용해서 문제를 해결할 수 있다. 위에서도 언급했지만 n일차에는 강연 요청이 n일차 이상으로 부탁한 강연들만 할 수 있다. 따라서 가능한 조건 내에서 price를 PriorityQueue에 넣어준다. 가장 비싼 강연을 하는 것이 좋기 때문에 내림차순으로 정렬될 수 있도록 -1을 곱해서 queue에 넣어주는 것이 핵심이다.

또한 문제에서 Lecture를 day 기준으로 정렬했기 때문에 0번째 index에 있는 강연이 현재 상태로는 가장 널널한 강의일 것이다. 따라서 그 때의 day부터 시작하여 day가 1이 될때까지 하나씩 감소시켜가면서 문제를 해결해주면 된다.

3. 코드

이를 코드로 구현한 것은 아래와 같다.

import java.util.*;
class Lecture implements Comparable<Lecture>{
    int price, day;
    Lecture(int price, int day){
        this.price=price;
        this.day=day;
    }
    public int compareTo(Lecture a){
        if (a.day!=this.day){
            return a.day-this.day;
        }
        else{
            return a.price-this.price;
        }
    }
}
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Lecture a[]=new Lecture[n];
       
        for(int i=0; i<n; i++){
            a[i]=new Lecture(sc.nextInt(), sc.nextInt());
        }
        PriorityQueue<Integer> q = new PriorityQueue<>();
        Arrays.sort(a);
        int maxday=0; //아무 강의요청도 없을 수 있기 때문에
        if(n>0){
            maxday=a[0].day;
        }
        int cur=0;
        int ans=0;
        for(int i=maxday; i>=1; i--){
            while(cur<n && a[cur].day==i){
                q.offer(a[cur].price*-1);
                cur++;
            }
            if (!q.isEmpty()){
                ans+=q.poll()*-1;
            }
        }
       System.out.println(ans);
        
    }
}