[G4] 백준 12892번 생일 선물 C++ 투 포인터, 정렬

리뷰

 

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

전형적인 투 포인터 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 선물의 개수를 저장할 변수
• d : 최소 가격차를 저장할 변수
• PV : 선물의 가격과 만족도를 정의할 구조체, 선물의 가격을 기준으로 오름차순 정렬한다.
• pvs : 선물들의 가격과 만족도를 저장할 PV타입 배열

 

함수

없음

 

 

문제풀이

1. n, d값을 입력 받고, n개의 선물의 가격과 만족도를 입력 받아 pvs배열을 초기화한다.
2. sort함수를 통해 pvs배열을 오름차순으로 정렬한다.
3. 변수 l, r을 0으로 초기화하고, cv를 pvs[0]의 만족도로, mx를 cv로 초기화한다.
4. r을 전위증가한 값이 n보다 작을 경우를 조건으로 하는 while루프를 수행한다.
5. 매 루프마다 cv에 pvs[r]의 만족도를 더해준다.
6. pvs[l]의 가격 + d가 pvs[r]의 가격 이하인 경우를 조건으로 하는 while루프를 수행한다.
7. 매 루프마다 cv에서 pvs[l]의 만족도를 제거하고, l을 전위증가시킨다.
8. 위 루프가 종료된 후 mx가 cv보다 작을 경우 mx를 cv로 변경한다.
9. 모든 탐색을 마친 후 mx에 저장된 값을 출력한다.

 

트러블 슈팅

1. mx를 long long타입으로 지정했지만 cv를 long long타입으로 지정하지 않아 WA를 받았다.
2. cv, mx를 모두 long long타입으로 지정하여 AC를 받았다.

 

참고 사항

1. 최대 10억까지의 수들이 들어오므로 cv, mx는 long long타입으로 정의해야 한다.
2. 가격을 기준으로 오름차순 정렬 후 l과 r의 가격 차가 d이상이 안나는 범위에서 만족도의 최대 합을 구해주었다.

 

정답 코드

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

const int N = 1e5;
int n, d;
struct PV {
	int p, v;
	bool operator<(const PV& other) const {
		return p < other.p;
	}
};
PV pvs[N];

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

	cin >> n >> d;
	for (int i = 0; i < n; ++i) {
		int p, v; cin >> p >> v;
		pvs[i] = { p, v };
	}
	sort(pvs, pvs + n);

	int l = 0, r = 0;
	long long cv = pvs[0].v;
	long long mx = cv;
	while (++r < n) {
		cv += pvs[r].v;

		while (pvs[l].p + d <= pvs[r].p) {
			cv -= pvs[l].v;
			++l;
		}

		if (mx < cv) mx = cv;
	}
	cout << mx;
}