백준 1781번(JAVA)

처음엔 이 문제를 그리디 알고리즘에 넣어야 하나, 우선순위 큐 카테고리로 넣어야 하나 고민했다.

근데 뭐 큰 의미없는 거 같아서 걍 그리디 알고리즘에 넣는다.

처음에는 그냥 단순히 마감시간이 적은것이 큰 우선순위를 갖도록, 그리고 마감시간이 같다면 컵라면 개수 많이주는걸 우선순위가 크게 우선순위큐에 넣었다.

예제는 잘 통과했는데 바로 틀렸다.

이유는 만약 문제가4개라 할떄

 

문제번호	1	2	3	4
데드라인	1	1	2	2
컵라면 개수	10	20	100	100

 

이런 경우에서 자연스럽게 데드라인 1중 컵라면개수가 더 많은 20을 택한다. 그리고 흘러간시간을++해준다.

그 후, 데드라인 2중에서 하나를 택해서 100을 골라서 총 컵라면개수는 120개가 된다.

하지만 사실 처음에 3번을 풀고 그 다음에 4번을 풀면 200개를 얻을 수 있다.

위와 같은 반례가 존재해서 다시 처음부터 생각해야했다.

---

 핵심은 바로 애초에 입력을 정렬하는것이다.

 cup이라는 객체를 만들어서 dead,count. 각각 데드라인과, 컵라면개수를 나타내는 변수를 가지고 있는 cup객체를 선언한다. 선언 할 때 compareTo를 써서 dead라인이 작은것이 가장 앞으로 가게 선언해준다

ArrayList<cup> arr선언해줘서 cup이라는 객체를 가지고 있는 ArrayList를 만들어준다.

그 후 입력을 다 받고 Collections.sort로 ArrayList를 정렬해주면, Arraylist 맨 앞부터 데드라인이 적은것부터 들어간다.

이 때 사실 데드라인이 같을시에는 컵라면개수가 많은 것이 앞으로 가게 해준다.(사실 데드라인이 같을시는 따로 구분안해줘도된다)

그 후 모든 ArrayList를 모두 탐색한다.

우선순위 큐는 우선 가장 작은값이 가장 큰 우선순위를 갖게한다.

위의 예시를 그대로 보며 어떻게 구현했는지 설명하겠다.

우선 데드라인이 가장작은거부터 시작하므로 문제번호 1번부터~4번까지의 순서다.

일단 1번의 컵라면개수 10을 q에 넣는다.

이 때 q사이즈는 1이 증가한다.

우선순위 큐

10

그 후 다음 문제번호 2번을 추가한다.

이 때 q사이즈는 또한 1이 증가한다.

우선순위 큐

10

20

하지만 문제번호 2번의 데드라인은 1이다. 이미 2초를 실행시켰는데 데드라인은 1이므로 데드라인<q.size() 이다.

q의 사이즈가 바로 여태까지 실행한 시간으로 생각하면 된다

새로들어온 수의 데드라인이 q.size()보다 작을때 q.poll()을 실행해준다.

우선순위 큐

20

다음 문제번호 3번을 추가한다.

q사이즈는 당연히 1이증가한다.

우선순위 큐

20

100

문제번호 3번의 데드라인은 2이므로 q.size()보다 작지 않다.

그러므로 q.poll()은 실행하지않는다.

 

다음 문제번호 4번을 추가한다.

우선순위 큐

20

100

100

문제번호 4번의 데드라인은 2인데 q.size()보다 작다

그러므로 q.poll()을 실행한다.

우선순위 큐

100

100

 

이제 우선순위 큐가 빌때까지 계속 q.poll()을 실행해주며 결과값에 더해준다.

 

 

소스코드

import java.util.*;
import java.io.*;
class cup implements Comparable<cup>
{
	int dead;
	int count;
	public cup(int dead,int count)
	{
		this.dead=dead;
		this.count=count;
	}
	public int compareTo(cup o)
	{
		if(dead==o.dead)
		{
			return o.count-count;//마감기한이 같다면 
		}
		else//마감기한이 짧은게 앞으로 간다.
		{
			return dead-o.dead;
		}
	}
}
public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		String[] s;
		PriorityQueue<Integer> q=new PriorityQueue<Integer>();
		ArrayList<cup> arr=new ArrayList<cup>();
		for(int i=0;i<N;i++)
		{
			s=br.readLine().split(" ");
			int dead=Integer.parseInt(s[0]);
			int count=Integer.parseInt(s[1]);
			arr.add(new cup(dead,count));
		}
		Collections.sort(arr);//마감기한이 가장 작은것이 작은인덱스로 간다.
		for(int i=0;i<N;i++)
		{
			int dead=arr.get(i).dead;
			int count=arr.get(i).count;
			q.add(count);
			if(dead<q.size())//q의사이즈는 여태까지 흘러간 시간, 시행한 시간이라고 생각한다.
			{
				q.poll();
			}
		}
		long result=0;
		while(!q.isEmpty())
		{
			result+=q.poll();
		}
		System.out.println(result);
	}
}

댓글과 지적은 언제든지 환영입니다~!

글이 마음에 들었다면 왼쪽 이미지를 눌러 후원 부탁드립니다><