취미로 코딩하기

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

이번에 볼 문제는 백준 25045번 문제인 비즈마켓이다.
문제는 아래 링크를 확인하자.

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

고객만족도가 0 미만인 거래를 하지 않는다는 조건이 없을 때, 거래를 정확히 K개 할 때의 고객만족도의 합의 최댓값은 (고객만족도가 높은 K개의 물품의 만족도 합) - (지불비용이 낮은 K개의 비용의 합)으로 계산할 수 있다.

모든 거래방법의 경우의 수는 거래 개수가 0개, 1개, ..., min(N,M)개 중 하나에 들어가므로, K를 0부터 min(N,M)까지 시도해 그중 최댓값을 구하는 것으로 문제의 답을 구해내자. 이중 (고객만족도 - 지불비용)의 값이 음수값이 나올 수밖에 없는 경우가 발생하면 그때의 고객만족도의 합은 위 과정에서 등장하는 최댓값 미만이 될 수밖에 없다는 점을 관찰하자. 해당 음수값이 나오는 쌍을 제외하면 더 큰 값의 고객만족도 합을 얻을 수 있기 때문이다.

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

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

int N, M;
int A[200000];
int B[200000];

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

	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < M; i++) cin >> B[i];

	sort(A, A + N);
	sort(B, B + M);
	int Aidx = N - 1, Bidx = 0;
	ll ans = 0, cur = 0;
	while (Aidx > -1 && Bidx < M) {
		cur += A[Aidx--] - B[Bidx++];
		ans = max(ans, cur);
	}

	cout << ans;
}