[백준/BOJ] 백준 15554번 : 전시회

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

15554번: 전시회

미술품의 크기와 가치를 저장해서 (크기, 가치)로 정렬한 뒤, 가치의 누적합을 계산한다.

 

B~A(B <=A) 구간의 값은 (B~A 가치의 합) - (A크기-B크기)으로 (누적합 A - 누적합 B-1) - (A크기 - B크기)가 된다. 즉 (누적합 A - A크기 - 누적합 B-1 + B 크기) 가 되는데, 이때 모든 지점을 확인하며 확인하는 지점을 A라고 놓고 A 이하의 수 중에서(- 누적합 B-1 + B크기) 값이 가장 큰 B를 찾는 방법으로 문제를 해결했다.

 

(- 누적합B-1 + B크기) 값이 가장 큰  B를 찾는 방법은 처음에 초기에는 B를 1이라 놓고, 각 지점(i)을 A라고 놓으며 확인할 때 확인하는 지점(i)과 B를 비교((-value_psum[B - 1] + info[B].first) <= (-value_psum[i - 1] + info[i].first)) 하여 B를 확인하는 현재 지점인 i로 하는 게 더 (- 누적합B-1 + B크기)를 크게 만드는 값인지를 판단하여 최적의 B를 찾는 방법으로 문제를 해결했다.

 

정렬을 할때, 크기가 같을 때 가치 순으로 정렬한 이유는 (- 누적합 B-1 + B크기)를 구할 때 B크기가 같은 구간이 있을 때 누적합(누적합 B-1)을 작게 하는 게 (- 누적합B-1 + B크기)를 더 크게 만들 수 있는데, 이때 가치가 작은 순으로 정렬돼야 크기가 같은 구간의 초반에서 더 작은 누적합(누적합 B-1)을 만들 수 있기 때문이다.

 

코드

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

int n;
vector<pair<long long, long long>> info(500005);
vector<long long> value_psum(500005, 0);

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

	cin >> n;

	for (int i = 1; i <= n; i++) {
		long long a, b;
		cin >> a >> b;

		info[i] = make_pair(a, b);
	}

	sort(info.begin() + 1, info.begin() + n + 1); //정렬

	//가치 누적합 계산
	for (int i = 1; i <= n; i++) {
		value_psum[i] = value_psum[i - 1] + info[i].second;
	}

	//B~A(B<=A)구간을 계산
	//(B~A가치의합) - (A크기-B크기)
	//(누적합A - 누적합B-1) - (A크기 - B크기)
	//누적합A - A크기 - 누적합B-1 + B크기
	//A를 하나씩 확인하면서, A이하의 수 중에서(- 누적합B-1 + B크기) 값이 가장 큰것을 찾는다

	int A, B;
	B = 1;
	long long result = 0;
	for (int i = 1; i <= n; i++) {
		A = i;
		
		if ((-value_psum[B - 1] + info[B].first) <= (-value_psum[i - 1] + info[i].first)) {
			B = i; //B를 현재의 i로 하는게 더 (- 누적합B-1 + B크기)를 더 크게 만드는 값일때
		}
		

		result = max(result, value_psum[A] - info[A].first - value_psum[B - 1] + info[B].first);
	}

	cout << result;

	return 0;
}