백준 - [BOJ 2109] 순회강연

백준 온라인 져지(BOJ)에서 제공 되는 2019번 문제는 그리디(Greedy, 탐욕법) 유형이다.

해당 문제는 code.plus 중급 1/3, 그리디 알고리즘에 게시된 문제이다.

---

문제

한 저명한 학자에게 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. 학자는 n개의 강연 요청을 받았다.

2. 강연 중 d일 안에 할 수 있는 강연을 선택해야한다.

3. 2번 중 p가 가장 높은 강연을 선택한다.

 

위와 같은 풀이를 정리 할 수 있는데 문제를 보면 0 <= n <= 10,000, 1 <= d <= 10,000, 1 <= p <= 10,000 이라는 조건이 추가된다. 그리고 하루에 최대 한 곳에서만 강연 할 수 있다는 조건이 존재한다.

 

제한시간은 2초이므로 n개의 (d, p)에 대해 모두 탐색해도 시간 내에 해결 할 수 있다.

접근

 

나는 처음 문제를 풀 때, 문제를 제대로 이해하지 못해서 d일 일 때 가장 큰 p를 선택하는 풀이를 작성했다.

하지만 아래 그림과 같은 문제점이 발생했다.

위와 같은 상황에서 가장 좋은 선택을 한다면 2일 안에 할 수 있는 강연 중 pay가 20과 30을 주는 경우를 선택할 수 있다.

우리는 1일차 강연을 꼭 수행하지 않아도 괜찮다.

해당 문제는 d일 안에 할 수 있는 강연을 선택 하는 것이다.

그 중에서도 pay가 가장 높은 강연을 선택하는 것이다.

 

즉, 해당 문제는 맨 마지막 강연날짜부터 접근하면 해결 할 수 있다.

n = 9

그림과 같이 n = 9일 때를 생각해보자. 

우리는 강연이 최대 10000일까지라는 정보를 알고 있다.

그럼 day가 4일이 될 때까지 아무런 조치도 하지 않는다.

 

day가 4일이 되었을 때 선택할 수 있는 경우가 생긴다.

1. 20, 30, 30 중에 가장 큰 값을 고른다. (30)

2. 해당 강연을 4일 때 진행한다.

day가 3일이 되었을 때 선택할 수 있는 경우가 생긴다.

1. 30, 40, 50, 20, 30 중에 가장 큰 값을 고른다. (50)

-> day 4까지의 강연들은 4일 내에 수행하면 되기 때문에 3일과 4일을 포함해서 선택한다.

2. 해당 강연을 3일차에 진행한다.

 

위와 같은 방법으로 풀이를 진행할 수 있다.

Brute-Force

/*
	dev-dot.tistory.com
	code.plus
	acmicpc 2109
*/
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<pair<int, int>> input(int &n) {
	vector<pair<int, int>> v;
	int p, d;
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> p >> d;
		v.push_back(make_pair(d, p));
	}
	
	return v;
}

int solve(vector<pair<int, int>> v) {
	int size = v.size();
	int totalPay = 0;
	vector<bool> visited(10001);
	
	for(int day = 10000; day > 0; day--) {
		int maxPay = 0;
		int lectIdx = -1;
		for(int lect = 0; lect < size; lect++) {
			// 방문할 예정 날짜가 지났으면 무시 
			if(v[lect].first < day) continue;
			// 방문했으면 무시 
			if(visited[lect]) continue;
			// 오늘 날짜 중 선택할 수 있는 가장 큰 페이 선택 
			if(maxPay < v[lect].second) {
				maxPay = v[lect].second;
				lectIdx = lect;
			}
		}
		if (lectIdx != -1) {
			totalPay += maxPay;
			visited[lectIdx] = true;
		}
	}
	
	return totalPay;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	
	int n;
	vector<pair<int, int>> v = input(n);
	cout << solve(v);
	
	return 0;
}

위와같이 모든 날짜(d)에 대해 해당 강연을 수행할 수 있는지 확인하는 방법을 Brute-Force라고 한다.

 

효율적인 풀이

 

모든 방식을 탐색하면 시간이 오래 걸린다는 단점이 있으므로 효율적인 풀이를 진행해보겠다.

 

이전 풀이에서 시간효율성에 있어서 가장 큰 문제점은 2가지가 있다.

1. 정렬이 되어있지 않아서 모든 값에 대해 탐색해야하는 문제점

2. 정렬을 하더라도 d일에 대한 가장 큰 p를 찾을 때마다 또 정렬을 해야하는 문제점

 

우리는 정렬을 한다면 x일부터 10000일까지만 탐색을 하면 된다.

정렬을 하지 않는다면 1일부터 10000일까지 모두 탐색을 해야한다.

 

그렇지만 위 풀이에서 d일 ~ d_max일마다 계속해서 정렬하게 된다면 N^2 log N이라는 더 비효율적인 결과가 나올 것이다.

그래서 우리는 heap 자료구조를 사용할 수 있다.

heap 자료구조는 자료구조 설명을 참고해주세요. (포스트 작성일 기준 아직 작성하지 못함.)

 

heap 자료구조를 이용한 Priority_queue를 사용하면 위의 문제점을 모두 해결할 수 있다.

가장 큰 data는 항상 queue의 front에 존재하므로 이 점을 이용하면 총 NlogN의 효율적인 연산을 기대할 수 있다.

 

priority_queue

/*
	authored by jihwankim
	dev-dot.tistory.com
	code.plus
*/
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

priority_queue<pair<int, int>> input(int &n) {
	priority_queue<pair<int, int>> pq;
	int p, d;
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> p >> d;
		pq.push(make_pair(-d, p));
	}
	
	return pq;
}

int solve(priority_queue<pair<int, int>> &pq) {
	priority_queue<int> allPay;
	int day, pay;
	int today = 1;
	
   	// 1일부터 d_max까지 강연을 탐색
	while(!pq.empty()) {
		day = -pq.top().first;
		pay = pq.top().second;
		pq.pop();
		
        // 가장 pay가 높은 강연의 유효일자가 지났을 경우
		if(day < today) {
        	// 현재까지 선택한 강연 중 현재 pay보다 적은 것이 있다면 교체
			if(-allPay.top() < pay) {
				allPay.pop();
				allPay.push(-pay);
			}
			continue;
		}
		
		allPay.push(-pay);
		today++;
	}
	
	int totalPay = 0;
	// 모든 pay에 대해 가격을 계산
    while(!allPay.empty()) {
		totalPay += (-allPay.top());
		allPay.pop();
	}
	
	return totalPay;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	
	int n;
	priority_queue<pair<int, int>> pq = input(n);
	cout << solve(pq);
	
	return 0;
}

 

다만 해당 문제는 앞에서 접근했다.

뒤에서 접근하는 방법도 있으므로 스스로 찾아보면 좋은 기회가 될 것 같다.

---

해결해 볼 수 있는 다른 풀이 방법

 

정렬을 이용해보기

brute-force 풀이에서 heap을 사용해서 풀어보기

 

참고할 포스트

 

아직 미작성

문제

 

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

2109번: 순회강연

https://code.plus/course/43

알고리즘 중급 1/3