BOJ - 1781 ) 컵라면

---

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

1781번: 컵라면

---

각 데드라인이 정해져있는 문제에서 최대한 많은 컵라면을 받으며 문제를 풀었을때 받을수있는 컵라면의 

 

개수를 구하는 문제이다. 처음 바로생각난것을 정렬+ 그리디인데, 분명 반례가 존재한다는 것을 알고

 

우선순위큐에 모든 노드를 넣은후 Time을 증가시키면서 Time보다 작은 라면들을 선택하면서 진행해보았다.

---

첫번째 시도

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static class node{
		int time, raman;

		public node(int time, int raman) {
			super();
			this.time = time;
			this.raman = raman;
		}
		
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		PriorityQueue<node> pq = new PriorityQueue<node>( new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				if(o1.time > o2.time) return 1;
				else if(o1.time < o2.time) return -1;
				else {
					if(o1.raman > o2.raman) return -1;
					else return o2.raman - o1.raman;
				}
			}
		});
		
		for(int i = 0 ; i < n ; i++) {
			st= new StringTokenizer(br.readLine());
			pq.add(new node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		int answer = 0;
		int cur = 0;
		while(!pq.isEmpty()) {
			node now = pq.poll();
			if(now.time > cur) {
				cur++;
				answer +=now.raman;
			} else {
				continue;
			}
		}
		System.out.print(answer);
		
	}

}

---

결과는 9%에서 터졌다!

 

---

 

사실 현재의 보상을 포기하고 미래의 문제를 풀었을때 받는 보상이 큰 경우가 존재한다. 

예를들어서 

 

1 2 3 4 4 4 5 의 deadline을 가지고있는 문제들이

2 2 2 10 10 10 1 의 컵라면보상을 가지는 경우이다. 

 

이런경우 앞에 3일을 포기하고 데드라인이 4인문제를 푸는 경우가 최대가 됨을 바로알수있다.

 

따라서 같은 시간이 만났을때 내가 이전에 풀었던 것들중에서 가장작은것과 현재 같은시간에 만나서 

 

받을수있는 라면의 개수중 더큰쪽을 취하고, 이전것은 버리면된다.

 

현재까지 받았던 라면의개수를 우선순위큐에 넣고 항상 제일 작은 값이 정렬되어 peek에 오도록한다.

 

같은시간의 값을 만났을때, 이 peek값과 비교하여 버릴것인지, 진행할 것인지 판단하는 알고리즘으로 짰다.

---

두번째 시도!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static class node{
		int time, raman;

		public node(int time, int raman) {
			super();
			this.time = time;
			this.raman = raman;
		}
		
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		
		
		ArrayList<node> al = new ArrayList<>();
		for(int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(br.readLine());
			al.add(new node (Integer.parseInt(st.nextToken()) , Integer.parseInt(st.nextToken())));
		}
		
		Collections.sort(al, new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				if(o1.time > o2.time) return 1 ;
				else if(o1.time < o2.time) return -1;
				else return 0;
			}
		});
		
		PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1 > o2) return 1;
				else if( o1== o2) return 0;
				else return -1;
			}
		});
		
		int answer = 0;
		int deadline =0;
		
		for(int i = 0 ; i < n ; i++) {
			int time = al.get(i).time;
			int ramen = al.get(i).raman;
			if(deadline < time) {
				answer += ramen;
				pq.add(ramen);
				deadline++;
			} else if(deadline == time) {
				int top = pq.peek();
				if(top < ramen) {
					answer -=top;
					pq.poll();
					answer += ramen;
					pq.add(ramen);
				}
			}
		}System.out.print(answer);
		
	}
}

---

1트는 힘들구나 ㅠ