[BOJ] 백준 1781번 컵라면 (Java)

#1781 컵라면

난이도 :  골드 2

유형 : 그리디

1781번: 컵라면

▸ 문제

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

 

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.

▸ 입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

▸ 출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

 

문제 풀이  

해당 문제를 데드라인을 정렬 후 최종 일까지 얻을 수 있는 최대 라면의 수를 bottom-up하는 DP로 접근할 수도 있지만 이보다 더 간단하고 빠르게 그리디로 풀이할 수 있는 방법이 있다.

 

이런 문제를 탐욕적으로 해결하는 방법은 몇 가지 떠올릴 수 있다.

1. i일에 가장 많은 컵라면을 주는 문제 풀기
2. i일동안 컵라면을 많이주는 순대로 i개 문제 풀기

1번 같은 경우, 해당 일만 고려해서 풀이를 하는 방법인데 반례로는 2일- (3,5), 3일 -(7,8)인 경우가 있다. 해당 방법으로는 2일-(3,5), 3일-8을 고르게 되는데 최적해는 (5,7,8)이다.

 

그러므로 2번의 방식을 사용해줘야 한다. i일동안 풀 수 있는 모든 문제를 고려하여 i개 문제를 선택하는 것이다. 

1. 현재 i일 동안 풀 수 있는 문제를 모두 우선순위 큐(최소 힙)에 저장한다.
2. 푸는 문제의 수가 i일 초과하면 가장 적은 라면을 주는 문제를 지운다.
3. 최종 데드라인까지 반복한다.

해당 탐욕적인 선택 방식은 i일에 가장 많은 라면을 주는 문제를 포함하기 때문에 최적해가 반드시 존재함을 알 수 있다. 즉, '손해'를 볼 일이 없는 방식인 것이다. 또한 자연스럽게 i일 최대 라면을 주는 문제를 선택하기 때문에 항상 최적의 선택을 함을 알 수 있다.

 

설계

1. Map 자료구조에 <데드라인, 라면 수>를 key, value로 저장한다.
2. 데드라인 기준으로 오름차순으로 정렬한 후 탐색한다. Collections.sort(keySet);
3. 해당 deadline일에 풀 수 있는 문제를 최소 힙에 저장한다. pq.add(num);
   1. 만약 deadline보다 풀 수 있는 문제의 수가 초과한다면 가장 적게주는 라면의 수를 제거한다. while(pq.size()>deadline)
4. 모든 탐색이 끝났으면 최소 힙에 담겨져 있는 문제의 수를 출력하여 더해준다. total+= pq.poll();

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws  IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		Map<Integer, List<Integer>> map = new HashMap<>();
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			if(map.containsKey(d)) {
				map.get(d).add(e);	
			}else {
				List<Integer> list = new ArrayList<>();
				list.add(e);
				map.put(d, list);
			}
		}
		
		List<Integer> keySet = new ArrayList<>(map.keySet());
		Collections.sort(keySet);
		
		Queue<Integer> pq = new PriorityQueue<>();
		for(int deadline : keySet) {
			for(int num : map.get(deadline)) {
				pq.add(num);
				while(pq.size()>deadline) {
					pq.poll();
				}
			}
		}
		int total=0;
		while(!pq.isEmpty()) {
			total+= pq.poll();
		}
		System.out.println(total);
	}
}