취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6134번 문제인 Sunscreen이다.
문제는 아래 링크를 확인하자.

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

가장 spf값이 큰 로션부터 보면서, 이 로션을 바를 수 있는 소 중 아래쪽 bound가 가장 적게 남은 소들에게 해당 로션을 발라주는 것이 최적해 중 하나이다. 다른 소에게 해당 로션을 발라준다면 앞으로 나올 spf이 더 작아진 로션을 바를 기회가 더 적어진다는 점을 관찰하면 위의 내용을 쉽게 이해할 수 있다.

아래는 제출한 소스코드이다.

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

int N, M; // N: 소 마릿수, M: 로션 수
pair<int, int> cows[2500]; // {L,R}
pair<int, int> lotions[2500]; // {SPF, 개수}
priority_queue<int> pq;

bool comp(pair<int, int>& p1, pair<int, int>& p2) {
	return p1.second < p2.second;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> cows[i].first >> cows[i].second;
	}
	for (int i = 0; i < M; i++) {
		cin >> lotions[i].first >> lotions[i].second;
	}

	sort(cows, cows + N, comp);
	sort(lotions, lotions + M);

	int ans = 0;
	int cowidx = N - 1;
	for (int l = M - 1; l > -1; l--) {
		int spf = lotions[l].first, cnt = lotions[l].second;
		while (cowidx > -1) {
			if (cows[cowidx].second >= spf) {
				pq.push(cows[cowidx].first);
				cowidx--;
			}
			else break;
		}
		while (!pq.empty()) {
			if (pq.top() > spf) pq.pop();
			else break;
		}
		while (!pq.empty() && cnt--) {
			ans++;
			pq.pop();
		}
	}

	cout << ans;
}