🔗 Problem

https://www.acmicpc.net/problem/2109

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 순회강연

public class BJ2109 {

	static class Lecture implements Comparable<Lecture>{
		
		int day;
		int fee;
		
		Lecture(int fee, int day){
			this.day = day;
			this.fee = fee;
		}

		@Override
		public int compareTo(Lecture o) {
			if(this.fee == o.fee) return this.day - o.day;
			else return o.fee - this.fee;
		}
	
	}
	
	static int n;
	static PriorityQueue<Lecture> queue = new PriorityQueue<>();
	static int total;
	static boolean[] visited = new boolean[10001];
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			queue.add(new Lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			
		}

		while(!queue.isEmpty()) {
			Lecture poll = queue.poll();
			for(int i = poll.day; i >= 1; i--) {
				if(visited[i] == false) {
					visited[i] = true;
					total += poll.fee;
					break;
				}
			}
		}
		
		System.out.println(total);
	}
}

📌 Note

아이디어

• 아이디어가 바로 떠오르지 않아 좀 고민했는데 잘 풀었다~
• 우선순위 큐를 사용해서 fee 기준 내림차순 정렬 후,
  queue.poll()의 day가 3이라면, 3일 안에 즉 1, 2, 3일에 강연할 수 있는지
  visited[]를 통해 체크했다.

// 골고루 풀기 위해 요즘 Greedy와 String 유형 위주로 풀고 있다.