[백준/BOJ] 백준 12003번 : Diamond Collector (Silver)

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

12003번: Diamond Collector (Silver)

 

두 구간을 정하는데, 두 구간 모두 구간에서 다이아몬드 사이 차이가 k이하여야 하고, 두 구간의 합이 최댓값이 되는 값을 구하는 문제이다.

 

우선 투 포인터를 이용해 max_range에 max_range[i] = "i번 다이아몬드부터 오른쪽으로 최대 범위의 개수"를 구하고 right_max_range에 right_max_range[i] =  i이상의 값 j(i, i+1, i+2,... )에 대하여 max_range[j] 의 최댓값을 저장해 놓는다. 이를 두 구간을 정할 때 사용하는데, 우선 첫 번째 구간의 시작점을 모든 지점으로 확인해 보면, 해당 시작점을 시작으로 하는 최대 구간의 범위를 max_range를 통해 알 수 있다. 그럼 다음 구간의 시작점은 i + max_range[i] 이후 위치 중에 골라야 하는데, 다음 구간의 시작점이 될 수 있는 곳 중 최대 범위의 크기는 right_max_range을 이용해 알 수 있다.

 

코드

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

int n, k;
vector<int> diamond;
int max_range[50005]; //[i] = i번 다이아몬드부터 오른쪽으로 최대 범위의 개수
int right_max_range[50005]; //[i] = i이상의 값 j(i, i+1, i+2, ... )에 대하여 max_range[j] 중 최댓값

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

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		diamond.push_back(input);
	}

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

	int left = 0;
	int right = 0;
	while (1) {

		if (left == right) {
			right++;
		}

		if (right == n) {
			for (int i = left + 1; i < n; i++) {
				max_range[i] = n - 1 - i; //left 이상의 값들은 모두 n-1까지 범위가 만들어질 수 있다
			}
			break;
		}

		if (diamond[right] - diamond[left] <= k) {
			max_range[left] = right - left;
			right++;
		}

		else {
			left++;
			max_range[left] = max(max_range[left], max_range[left - 1] - 1); //left도 최소 left-1에서 오른쪽으로 범위가 되는곳 까지는 범위가 될 수 있다
		}
	}

	int max_value = 0;
	for (int i = n - 1; i >= 0; i--) {
		max_value = max(max_value, max_range[i]);
		right_max_range[i] = max_value;
	}

	int result = 0;
	for (int i = 0; i < n; i++) {
		//(i부터 최대 범위 a까지 크기) + (a+1 이후를 시작점으로 하는 최대 범위 크기)
		result = max(result, (1 + max_range[i]) + (1 + right_max_range[i + max_range[i] + 1]));
	}

	cout << result << "\n";

	return 0;
}