취미로 코딩하기

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

이번에 볼 문제는 백준 28284번 문제인 스터디 카페이다.
문제는 아래 링크를 확인하자.

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

벌 수 있는 최대 수익은 각 날에 스터디 카페에 찾아온 이용자 K명을 비용이 비싼 차례대로 K개의 좌석에 앉힐 때임을 쉽게 알 수 있다. 다만 모든 날에 대하여 이를 시뮬레이션하는 것으로는 문제를 충분히 해결할 수 없다. 10억일동안의 각 날에 대해 직접 계산하기에는 제한시간이 부족하기 때문이다.

위의 문제를 효율적으로 해결하기 위해 스터디 카페에 찾아오는 인원이 바뀌는 날들을 기준으로 기간을 나누는 방법을 생각하자. 이와 같이 나눌 경우, 각 나눠진 기간에 벌 수 있는 최대 수익은 (기간에 포함된 날의 수) * (해당 기간의 각 날에 벌 수 있는 최대 수익)과 같이 구할 수 있음은 쉽게 관찰할 수 있다. 또한 하루의 최대 수익은 그 날 찾아오는 인원이 정해지면 변하지 않으므로 prefix sum을 이용해 전처리해 두면 프로그램을 빠르게 동작하게 할 수 있다.

최소 비용 또한 비슷한 방법으로 구해 문제를 해결하자.

문제의 답이 32비트 정수 자료형으로 표현할 수 있는 범위를 넘을 수 있음에 유의하자.

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

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int N, M;
ll cost1[500000], cost2[500000];
ll oldT, curcost; int cidx = -1;
vector<pair<ll, int>> sched;

ll ans1, ans2;

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

	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> cost1[i];
	sort(cost1, cost1 + N, greater<>());
	for (int i = 0; i < N; i++) cost2[i] = cost1[N - i - 1];
	for (int i = 1; i < N; i++) cost1[i] += cost1[i - 1];
	for (int i = 1; i < N; i++) cost2[i] += cost2[i - 1];

	while (M--) {
		int S, E; cin >> S >> E;
		sched.emplace_back(make_pair(S, 1));
		sched.emplace_back(make_pair(E + 1, -1));
	}

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

	for (auto& p : sched) {
		if (cidx >= 0) ans1 += (p.first - oldT) * cost1[cidx], ans2 += (p.first - oldT) * cost2[cidx];
		oldT = p.first;
		cidx += p.second;
	}

	cout << ans2 << ' ' << ans1;
}