[백준][알고리즘]순회강연-2109

문제출처 : https://www.acmicpc.net/problem/2109

 

문제설명

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

​

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

​

​

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

풀이

-> 해당 문제는 탐욕 알고리즘을 이용하여 풀이가 가능합니다.

​

1) 입력받은 강연료를 기준으로 내림차순으로 정렬을 하여 강연료가 큰 순서로 정렬해 줍니다.

2) 정렬된 데이터를 기준으로 강연료가 큰 방문일에 대해 방문 가능 여부를 체크하며 총 페이를 계산해준다.

​

여기서 많이들 헷갈리는 상황이 발생한다.

하루에 한곳만 방문을 하는 것은 맞으나 주어진 방문일은 꼭 그 날에 방문을 해야한다는 말이 아니다.

예를들어 아래와같이 3개의 데이터가 주어진 상황이다.

idx	강연료	방문일
0	1	1
1	10	2
2	10	2

이 때 보통 헷갈리는 부분이 1일차에는 idx=0인 강연료 1과 2일차는 idx=1or 2인 것을 골라 답으로 11로 제출하는상황이 발생한다.

하지만 주어진 문제에서는 방문일 기간안에만 방문하면 된다는 의미이다. 위의 예시에 데이터 기준으로 강연료가 가장 큰 idx=1,2를 보면 모두 2일안에만 방문하면 된다는 이야기이다. idx=1을 선택하고 나서 다시 idx =2를 선택해도 두 선택지 모두 2일안에 방문하는 조건을 만족하게 되는 것이다. 그래서 위와 같은 예시의 정답은 20이 되게 된다.

이 문제의 반례사례를 보면 위와 같이 착각하는 경우가 대다수이다.

public class Greedy2109Alpha {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int cnt = Integer.parseInt(st.nextToken());
		
		ArrayList<Lecture> list = new ArrayList<>();
		for(int i=0; i< cnt;i++) {			
			st = new StringTokenizer(br.readLine());
			int pay = Integer.parseInt(st.nextToken());
			int day = Integer.parseInt(st.nextToken());			
			list.add(new Lecture(pay, day));
		}		
		Collections.sort(list, Collections.reverseOrder()); //(list);
		
		boolean[] check = new boolean[10001];
		
		int resMoney = 0; 
		for(int i=0; i<list.size();i++) {
            // 위의 2번 풀이에 대한 부분		
			for(int j = list.get(i).day ; j>=1; j-- ) {				
				if(!check[j]== true ) {
					resMoney = resMoney + list.get(i).pay;
					check[j] = true;
					break;
				}
			}
		}		
		System.out.println(resMoney);		
	}
	static class Lecture implements Comparable<Lecture>{
		
		int day;
		int pay;
		
		public Lecture(int pay, int day) {
			this.day = day;
			this.pay = pay;					
		}

		@Override
		public int compareTo(Lecture o) {
			return this.pay -o.pay;
		}		
	}
}