[BOJ] 백준 1781 컵라면 (JAVA)

우선순위 큐 + 그리디!

📑 문제

백준 1781 컵라면

---

🌱 아이디어

데드라인 별 가장 최적의 값을 선택하여 최댓값을 출력하는 문제! 그리디 알고리즘이다!
정렬속도가 빠른 우선순위 큐를 이용해 보자!

 

문제 자체는 이해하기도 쉽고 어렵지 않았다. 덕분에 그리디, 우선순위큐를 이용하면 되겠다는 생각도 빨리 도출해 내었던 문제이다.

하지만 깊게 생각을 해야 하는 문제였다 ㅠ 다음 예제를 보자

 

반례 1) 

4
1 50
2 30
3 60
3 70

ans = 180

 

가장 처음 구현했을 때 데드라인을 1 ~ N까지 오름차순 데드라인별 최적값을 구하는 형식으로 풀었지만

결과는 150이 나왔다. 50 + 30 + 70 이렇게 컵라면을 획득한 것이다.

 

하지만 문제의 정답은 50 + 60 + 70 = 180 이다. 즉 가장 낮은 데드라인이 항상 최적의 값을 보장하지 않기 때문에

N ~ 1까지 데드라인이 큰 수부터 낮은 순으로 최적값을 찾아야 한다.

 

정리를 하자면 이렇다

 

1. 데드라인은 그리디 방식이 아닌 뒤에 나올 값까지 포함해서 최적값을 찾아야 한다.

2. 컵라면 개수는 그리디 방식으로 가장 최댓값만 가져오면 된다.

 

이제 구현을 해보자!

---

🌱 코드 및 풀이

	public class Main {
	public static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
	public static PriorityQueue<node> box = new PriorityQueue<node>();
	public static class node implements Comparable<node> {
	int dl, ramen;
	public node(int dl, int ramen) {
	this.dl = dl;
	this.ramen = ramen;
	}
	@Override
	public int compareTo(node o) {
	return o.dl - dl;
	}
	}
	public static void main(String[] args) throws IOException { //조건 입력
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	int N = Integer.parseInt(br.readLine());
	long cnt = 0;
	for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine(), " ");
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	// box 우선순위 큐에 데드라인 기준으로 내림차순으로 정렬한다.
	box.offer(new node(a, b));
	}
	// 데드라인 범위 지정.
	int deadLine = box.peek().dl;
	while (deadLine !=0) {
	// 현재 deadLine 값 기준으로 해당되는 컵라면 pq 우선순위에 입력
	while (!box.isEmpty() &&deadLine == box.peek().dl) {
	pq.offer(box.poll().ramen);
	}
	// pq는 내림차순으로 정렬되어있기 때문에 가장 많은 컵라면 cnt에 더하기.
	if (!pq.isEmpty()) {
	cnt += pq.poll();
	}
	// 하나의 문제를 풀었기 때문에 deadLine 범위를 좁혀준다.
	deadLine--;
	}
	System.out.print(cnt);
	}
	}

view raw 컵라면.java hosted with ❤ by GitHub

 

1.  데드라인을 내림차순으로 pq에 입력하기 위해  box 우선순위 큐에 담는다

2.  현재 deadLine에 해당하는 문제들 입력받고 그리디 방식으로 최댓값 도출!

3.  deadLine에 -1씩 해주면서 최댓값 도출

4.  deadLine 해당하는 문제가 box.peek에 있다면 2번으로 복귀.

 

---

🌱 느낀 점

 

복잡한 문제는 아니었지만 반례가 없었다면 풀기 힘들었을 것 같다.

골드 상위 문제는 새로운 개념을 가지고 푸는 문제들이 많다  특히 자료구조 문제가 그런 것 같다 ㅎㅎ

한동안 그래프 탐색 알고리즘이 재미있었는데 요즘은 자료구조문제 푸는 게 더 재미있다 ㅎㅎ 새로운 아이디어를 배우는 느낌이다 ㅎ