[백준] 1781 컵라면

⚡백준 1781 컵라면

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

틀린 풀이

• 숙제를 데드라인이 빠른 순으로, 데드라인이 같다면 얻을 수 있는 컵라면이 많은 순으로 정렬
  -> 데드라인이 빠른 숙제부터, 그 숙제의 데드라인 내에 할 수 있는 숙제의 수만큼 숙제를 하는 그리디 알고리즘을 설계하였다

• 반례(https://www.acmicpc.net/board/view/6365)
  input:
  9
  5 5
  4 6
  4 12
  3 8
  4 18
  2 10
  2 5
  1 7
  1 14
  output: 55
  answer: 65

• 내가 구현한 그리디 알고리즘:
  숙제 정렬: (1, 14), (1, 7), (2, 10), (2, 5), (3, 8), (4, 18), (4, 12), (4, 6), (5, 5)
  현재 시간 0 ~ 데드라인 1: (1, 14) 선택
  현재 시간 1 ~ 데드라인 2: (2, 10) 선택
  현재 시간 2 ~ 데드라인 3: (3, 8) 선택
  현재 시간 3 ~ 데드라인 4: (4, 18) 선택
  현재 시간 4 ~ 데드라인 5: (5, 5) 선택
  -> 총 얻을 수 있는 컵라면 수: 14 + 10 + 8 + 18 + 5 = 55

• 답:
  (1, 14), (2, 10), (4, 18), (4, 12), (5, 5) 선택
  -> 총 얻을 수 있는 컵라면 수: 14 + 10 + 18 + 12 + 5 = 59
  -> 각 데드라인의 숙제를 반드시 하나씩 선택해야하는 것은 아니다

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int cnt = 0;

//<숙제 데드라인, 얻게되는 컵라면 수>
vector<pair<int, int>> hw;

//데드라인 빠른 순서대로 정렬
//데드라인 같다면 컵라면 수 많은 순서대로 정렬
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
	if (a.first < b.first) return true;
	if (a.first == b.first) return a.second > b.second;
	return false;
}

//lower_bound를 위한 pair 비교 함수
bool paircmp(const pair<int, int>& a, const pair<int, int>& b) {
	return a.first < b.first;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int deadline, cup;
		cin >> deadline >> cup;
		hw.push_back(make_pair(deadline, cup));
	}
	//숙제 정렬
	sort(hw.begin(), hw.end(), cmp);

	//현재 시간
	int curtime = 0;
	//현재 할 수 있는 숙제의 인덱스
	int index = 0;
	while (index < n) {

		int deadline = hw[index].first;
		
		//현재 데드라인 내에서 할 수 있는 숙제의 개수만큼 숙제를 한다
		int num_of_hw = deadline - curtime;
		for (int i = 0; i < num_of_hw; ++i) {
			if (index == n) break;

			cnt += hw[index].second;
			index++;
		}

		curtime = deadline;
		//현재 데드라인 이후 할 수 있는 숙제의 인덱스
		int next_index = upper_bound(hw.begin(), hw.end(), make_pair(deadline, 0), paircmp) - hw.begin();
		index = next_index;
	}

	cout << cnt;
	return 0;
}

⚡풀이

• 현재 시간 1: 데드라인 1인 숙제 ~ 데드라인 N인 숙제 중 하나를 선택할 수 있다
  현재 시간 2: 데드라인 2인 숙제 ~ 데드라인 N인 숙제 중 하나를 선택할 수 있다
  ...
  현재 시간 N-1: 데드라인 N-1인 숙제 ~ 데드라인 N인 숙제 중 하나를 선택할 수 있다
  현재 시간 N: 데드라인 N인 숙제 중 하나를 선택할 수 있다

• 현재 시간을 역순으로 생각하여 데드라인이 현재 시간인 숙제들을 maxheap에 추가
  -> 현재 시간에 선택할 수 있는 데드라인을 가진 숙제들이 maxheap에 저장된다

• 현재 시간 N: maxheap에 데드라인 N인 숙제 추가
  -> maxheap에 데드라인 N인 숙제 저장됨
  -> 컵라면 수 가장 큰 숙제 선택
  현재 시간 N-1: maxheap에 데드라인 N-1인 숙제 추가
  -> maxheap에 데드라인 N-1인 숙제 ~ 데드라인 N인 숙제 저장됨
  -> 컵라면 수 가장 큰 숙제 선택
  ...
  현재 시간 1: 데드라인 1인 숙제 추가
  -> maxheap에 데드라인 1인 숙제 ~ 데드라인 N인 숙제 저장됨
  -> 컵라면 수 가장 큰 숙제 선택

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;

int N;
//<숙제 데드라인, 숙제 컵라면>
vector<pair<int, int>> hw;

//총 얻을 수 있는 컵라면의 수
ull cnt = 0;
priority_queue<int> maxheap;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		hw.push_back(make_pair(a, b));
	}

	sort(hw.begin(), hw.end());

	//현재 시각 N부터 1까지 역순으로 생각한다
	for (int cur = N; cur > 0; --cur) {

		//hw 데드라인 오름차순으로 정렬됨 -> 역방향으로 순회
		for (int i = hw.size()-1; i >= 0; --i) {

			//현재 시각이 deadline인 hw의 컵라면 수 maxheap에 추가
			if (hw[i].first == cur) {
				maxheap.push(hw[i].second);
				hw.pop_back();
			}
			else break;
		}
		
        	//컵라면 수 가장 큰 숙제 선택
		if (!maxheap.empty()) {
			cnt += maxheap.top();
			maxheap.pop();
		}
	}
	
	cout << cnt;
	return 0;
}