백준(2109번) - 순회강연(Java) (그리디)

 그리디의 단골문제이다. 기한이 정해져 있고 최대의 이득을 취하는 그리디 알고리즘의 취지에 딱 맞는 문제다.

 

이런 문제는 어떤 기준으로 정렬기준이 굉장히 중요하다. 처음에 생각한 기준은

1순위 : 기한이 촉박한 것

2순위 : 기한이 같다면 페이가 센 것

 

그렇게 해서 완성했던 코드이다.

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


public class Main
{
	static class node implements Comparable<node>
	{
		int p;
		int d;
		
		public node(int p, int d)
		{
			this.p = p;
			this.d = d;
		}
		
		public int compareTo(node n)    //우선 기한이 촉박한 것부터, 같다면 페이가 센 걸로
		{
			if(d == n.d) return n.p - p;
			else return d - n.d;
		}
	}
	static long ans;
	static int n, day;
	static PriorityQueue<node> pq;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		pq = new PriorityQueue<>();
		
		for(int i = 0 ; i < n ; i++)
		{
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			pq.add(new node(a,b));
		}
		
		while(!pq.isEmpty())
		{
			node nod = pq.poll();
			
			if(day < nod.d)
			{
				day++;
				ans += nod.p;
			}
		}
		
		System.out.println(ans);
	}
}

테스트 케이스는 통과했으나, 반례를 뚫지 못했다.

20
85 8
56 11
58 12
28 20
36 12
45 9
55 4
1 3
71 6
72 15
38 9
76 20
67 5
78 2
48 18
100 3
16 2
7 10
95 5
42 14

answer : 1050

 

 역으로 최대 기한에서 타고 올라가는 방식도 생각했는데, 별반 다를 것 없어서 포기했다.

그래서 기준을 다르게 바꿨는데

1순위 : 페이가 센 것

2순위 : 같다면 기한이 촉박한 것

 

우선순위가 역전이 되었고 감정이입해 스케쥴 표에 작성하듯이 배열에다가 정리도 해줬다.

<문제>

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

 

<소스코드>

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


public class Main
{
	static class node implements Comparable<node>
	{
		int p;
		int d;
		
		public node(int p, int d)
		{
			this.p = p;
			this.d = d;
		}
		
		public int compareTo(node n)    //페이가 센 것 같다면 촉박한 순
		{
			if(p == n.p) return d - n.d;
			else return n.p - p;
		}
	}
	static long ans;
	static boolean[] sche = new boolean[10001];
	static int n;
	static PriorityQueue<node> pq;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		pq = new PriorityQueue<>();
		
		for(int i = 0 ; i < n ; i++)
		{
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			pq.add(new node(a,b));
		}
		
		while(!pq.isEmpty())
		{
			node nod = pq.poll();
			
			for(int i = nod.d ; i >= 1 ; i--)    //리미트부터 1일까지 더듬어 가며 가능한 날 표시
			{
				if(!sche[i])
				{
					sche[i] = true;
					ans += nod.p;
					break;
				}
			}
		}
		
		System.out.println(ans);
	}
}