[백준/BOJ] 백준 21279번 : 광부 호석

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

21279번: 광부 호석

x좌표를 기준으로 해당 x좌표에 속하는 y좌표와 아름다운 정도를 저장하고(vector<pair<int, int>> gold_x[100005]; //[x좌표] = (y좌표, 아름다운 정도)), y좌표를 기준으로 해당 y좌표에 속하는 x좌표와 아름다운 정도를 저장해서(vector<pair<int, int>> gold_y[100005]; //[y좌표] = (x좌표, 아름다운 정도)), x좌표와 y좌표를 기준으로 각각 좌표를 다루었다.

 

범위를 탐색하는 것은 x지점은 큰 쪽에서 작은 쪽으로 범위를 줄이고, y지점은 작은 쪽에서 큰 쪽으로 범위를 늘리는 방법으로 좌표에서 투 포인터를 응용했다. 즉 현재 범위에서 광물을 더 캘 수 있을 때는 y지점을 올리는 방향으로 y지점 포인터를 늘리고 현재 범위에서 광물이 캘 수 있는 광물보다 더 많을 때는 x지점을 줄이는 방향으로 x지점 포인터를 줄였다.

 

현재 범위에서 광물을 더 캘 수 있을 때 y지점을 올리는 방향이 아닌, x지점을 올리는 방향으로 범위를 늘릴 수 있지 않은지에 대한 생각을 할 수 있는데, 해당 x지점은 큰 쪽부터 시작해서 현재 y지점 이하인데도 불구하고 이미 캘 수 있는 광물보다 더 많은 범위를 포함한다고 판단되어 줄여진 지점이기 때문에 x지점을 늘리면 광물을 캘 수 있는 양 보다 더 많은 범위를 포함되기 때문에 x지점은 늘릴 수 없다.

 

마찬가지로 현재 범위에서 광물이 캘 수 있는 광물보다 저 많을 때 x지점을 줄이는 방향이 아닌, y지점을 줄이는 방향으로 범위를 줄이는 것을 생각할 수 있는데, 해당 y지점은 작은 쪽부터 시작해서 현재 x지점 이상인데도 불구하고 이미 더 광물을 캘 수 있다고 판단되어 늘려진 지점이기 때문에 y지점을 줄일 수 없다. 

 

코드

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

int n, c;
vector<pair<int, int>> gold_x[100005]; //[x좌표] = (y좌표, 아름다운 정도)
vector<pair<int, int>> gold_y[100005]; //[y좌표] = (x좌표, 아름다운 정도)
long long result;

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

	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int x, y, v;
		cin >> x >> y >> v;

		gold_x[x].push_back(make_pair(y, v));
		gold_y[y].push_back(make_pair(x, v));
	}

	//x지점은 큰쪽에서 작은쪽으로 범위를 줄이고, y지점은 작은 쪽에서 큰쪽으로 범위를 늘리는 투포인터로 범위 탐색
	int check_x = 100000; //check_x는 오른쪽 끝에서 왼쪽으로 움직이고(범위를 줄이는 방향)
	int check_y = 0; //check_y는 아래에서 위쪽으로 움직인다(범위를 늘리는 방향)
	
	long long check_value = 0;
	int check_cnt = 0;

	while (1)
	{
		//끝에 도달 했을때
		if (check_x < 0 || check_y > 100000)
			break;

		// check_cnt <= c일때 check_y를 위로 이동(범위를 늘림)
		// 초기에도 여기에 걸림
		if (check_cnt <= c) {

			//다음 위치인 check_y일때를 추가한다 (check_y는 현재 y위치의 다음 위치)
			for (int i = 0; i < gold_y[check_y].size(); i++) {
				if (gold_y[check_y][i].first <= check_x) { //해당 범위에 속할때
					check_cnt++;
					check_value += (long long)gold_y[check_y][i].second;
				}
			}
			check_y++; //한칸 위로 올라간다
		}

		// check_cnt > c일때 check_x를 왼쪽으로 이동(범위를 줄임)
		else {

			//현재 위치인 check_x일때를 뺀다 (check_x는 현재 x위치)
			for (int i = 0; i < gold_x[check_x].size(); i++) {
				if (gold_x[check_x][i].first <= check_y - 1) { //현재 check_y는 실제 y위치보다 한칸 위로 올라간 상태이므로 -1을 한다
					check_cnt--;
					check_value -= (long long)gold_x[check_x][i].second;
				}
			}
			check_x--; //한칸 왼쪽으로 이동한다
		}

		if (check_cnt <= c) {
			result = max(result, check_value);
		}
	}

	cout << result;

	return 0;
}