백준 - 순회강연

문제 설명

강연날짜를 잡아 최대 수익을 얻을 수 있을 값은 무엇인지 구하는 문제이다. 단, 강연은 하루에 한번만 가능하다.

 

풀이

우선순위에 이익이 큰 순서대로 담고 현재 마감일자를 기준으로 강의를 담아낼 수 있는지 체크한다.

마지막 날짜에 최대한 큰 이익을 낼 수 있는 강의를 하는 것이 최대 수익을 얻을 수 있다.

만약 같은 데드라인을 가지게 되고 2번쨰로 큰 수익구조를 가지고 있다면 데드라인 -1 을 하며 강연이 비어있는 곳을 찾아낸다.

수익구조가 많으면 최대한 마감날까지 Lazy하게 미뤄야 최대 수익 구조를 가질 수 있게 된다.

static class Node implements Comparable<Node>{
		int profit,deadLine;

		public Node(int profit, int deadLine){
			this.profit=profit;
			this.deadLine= deadLine;
		}

		@Override
		public int compareTo(Node o){
			return o.profit - this.profit;
		}

		public String toString(){
			return "profit: "+profit+", deadLine: "+deadLine;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(reader.readLine());
		int dayOfMax=0;
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		while (n-- > 0) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int profit=Integer.parseInt(st.nextToken());
			int deadLine=Integer.parseInt(st.nextToken());
			dayOfMax=Math.max(dayOfMax,deadLine);
			pq.offer(new Node(profit,deadLine));
		}

		int days[]=new int[dayOfMax+1];
		while(!pq.isEmpty()){
			Node cur=pq.poll();
			for(int i=cur.deadLine; i>0; i--){
				if(days[i]==0){
					days[i]=cur.profit;
					break;
				}
			}
		}

		int answer= Arrays.stream(days).sum();
		System.out.println(answer);
	}

 

다른 풀이

• 데드라인이 같은 것끼리 묶어서 우선순위에 얻을 이익들을 넣어준다. 그리고 최대 주어지는 마감 시간(10,000)을 시작으로 1씩 내려가며 데드라인에 따른 강의 수익들을 우선순위 큐에 넣어줘서 최대 수익을 얻을 수 있는 것들로만 담아낸다.

static PriorityQueue<Integer> pq;
    static ArrayList<Integer>[] lectureList = new ArrayList[10001];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        pq = new PriorityQueue<>(Collections.reverseOrder());

        int N = Integer.parseInt(br.readLine());

        for (int i = 1; i <= 10000; i++) {
            lectureList[i] = new ArrayList<>();
        }
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            lectureList[d].add(p);
        }

        int ans = 0;
        int time = 10000;
        while (time > 0) {
            pq.addAll(lectureList[time]);
            if (!pq.isEmpty()) {
                ans += pq.poll();
            }
            time--;
        }

        System.out.println(ans);
    }