[백준/BOJ] 백준 3090번 : 차이를 최소로

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

3090번: 차이를 최소로

 

이분 탐색 (매개 변수 탐색, Parametric Search)을 이용해 인접한 수의 차이가 특정 차이 이하로 만들 수 있는지 확인하는 방법을 통해 문제를 해결했다.

이때, 인접한 수의 차이를 특정 값(check_dist) 이하로 가능한지 판별하는 방법으로, 앞에서부터 뒤쪽으로 확인하며, (check_dist < 뒤쪽값 - 앞쪽값) 인지 확인해서, (check_dist < 뒤쪽값 - 앞쪽값) 조건에 성립한다면 뒤쪽값의 값을 줄이는 방법을 거치고 그 후 뒤에서부터 앞쪽으로 확인하며, (check_dist < 앞쪽값 - 뒤쪽값) 인지 확인해서, (check_dist < 앞쪽값 - 뒤쪽값) 조건에 성립한다면 앞쪽값의 값을 줄이는 방법을 통해 총값을 줄인 횟수가 t를 초과했는지 판별했다.

 

코드

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

int n, t;
vector<int> a;

//모든 인접한 수의 차이를 check_dist 이하로 가능한지 확인
bool Check(int check_dist) {

	long long down_cnt = 0;
	vector<int> check_a = a;

	//앞에서 뒤 쪽으로 확인
	for (int i = 0; i < check_a.size() - 1; i++) {

		if (down_cnt > t) {
			break;
		}

		int& here = check_a[i];
		int& there = check_a[i + 1];

		//there을 줄여야 될 때
		if (here + check_dist < there) {
			down_cnt += (there - here - check_dist);
			there -= (there - here - check_dist);
		}
	}

	//뒤에서 앞 쪽으로 확인
	for (int i = check_a.size() - 1; i >= 1; i--) {

		if (down_cnt > t) {
			break;
		}

		int& here = check_a[i];
		int& there = check_a[i - 1];

		//there을 줄여야 될 때
		if (here + check_dist < there) {
			down_cnt += (there - here - check_dist);
			there -= (there - here - check_dist);
		}
	}

	if (down_cnt > t) {
		return false;
	}

	return true;
}

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

	cin >> n >> t;

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

		a.push_back(input);
	}

	long long left = 0;
	long long right = 1000000000;
	int result_dist = -1; //인접한 수 차이 최댓값의 최소
	while (left <= right) {
		long long mid = (left + right) / 2;

		//인접한 수의 차이의 최댓값이 mid 이하로 가능한지 확인
		if (Check(mid)) {
			result_dist = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}

	//앞에서 뒤 쪽
	for (int i = 0; i < a.size() - 1; i++) {

		int& here = a[i];
		int& there = a[i + 1];

		//there을 줄여야 될 때
		if (here + result_dist < there) {
			there -= (there - here - result_dist);
		}
	}

	//뒤에서 앞 쪽
	for (int i = a.size() - 1; i >= 1; i--) {
		int& here = a[i];
		int& there = a[i - 1];

		//there을 줄여야 될 때
		if (here + result_dist < there) {
			there -= (there - here - result_dist);
		}
	}

	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}

	return 0;
}