백준 3090 차이를 최소로 풀이

문제

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

&Title
3090번 - 차이를 최소로부분 점수

&Question
정수 N개로 이루어진 배열 A가 주어진다. 상근이는 수열의 
수 하나를 골라서 값을 1 감소시킬 수 있다. 단, 
수는 1보다 작아질 수 없다.상근이는 위의 감소시키는 연산을 최대 
T번 하려고 한다. 이때, 인접한 수의 차이의 최댓값을 최소로 
하는 프로그램을 출력하시오. 

&Input
첫째 줄에 N과 T가 주어진다.(2 ≤ N ≤ 
100 000, 1 ≤ T ≤ 109)둘째 줄에는 배열에 
들어있는 수가 주어진다. (109보다 작은 자연수) 

&Output
첫째 줄에 인접한 수의 차이의 최댓값을 가장 작게한 
배열 A의 내용을 공백으로 구분하여 출력한다. 최대 T번 감소시켜야 
한다. 

&Example
-input
5 5
4 2 3 7 6

-output
3 2 3 4 5

요약

• 정수 n개의 배열이 주어진다.
• 최대 T번 수열의 수 하나를 골라서 값을 1 감소시킬 수 있다.(1보다 작아질순 없다.)
• 이때 인접한 수의 차이의 최댓값을 최소로 하는 경우를 출력하시오.

접근

• 이분탐색할 기준점을 뭐라 잡을것인가.. 인접한 수의 차이의 최댓값을 기준으로 할것인가? T연산을 해야하는 수열의 수를 이분탐색으로 찾을것인가? 전자가 범위가 더 작기 때문에 전자로 택한다.
• 여기서 문제가 발생하는데 인접한 수의 차이를 정했을때 어떤 수열을 얼마만큼 감소시키는가이다…
• 이는 생각보다 간단하다. 좌를 기준으로 차이만큼, 우를 기준으로 차이만큼 두번 검사해주면 해당 수열은 val만큼 인접한 수의 차이를 가지게 된다.

풀이

1. 이분탐색을 시행한다. r은 수열의 요소중 가장 큰원소로 해준다.
2. t번만에 해당 수열을 만들수있는지 확인하는 isRight함수 시행하여 확인한다.
3. 먼저 초기 선언에 cnt는 arr의 원소가 1e9이고 1e5의 개수이기 때문에 각 원소의 차이가 int의 범위가 넘을수도 있기 때문에 long long으로 선언해준다. 그리고 수열을 narr에 복사해준다.

    long long int cnt = 0;
    memcpy(narr, arr, sizeof(int) * n);
   

4. 양방향으로 최소 val만큼나게 배열을 수정해준다.
   1. 자기보다 오른쪽에 있는 값이 val보다 차이가 나면 오른쪽 값을 수정해준다.

       for (int i = 1; i < n; ++i) {
               if (narr[i - 1] + val < narr[i]) {
                   cnt += narr[i] - (narr[i - 1] + val);
                   narr[i] = arr[i - 1] + val;
               }
           }
      

   2. 자기보다 왼쪽에 있는 값이 val보다 차이나면 왼쪽 값을 수정해준다.

       for (int i = n - 1; i > 0; --i) {
               if (narr[i] + val < narr[i - 1]) {
                   cnt += narr[i - 1] - (narr[i] + val);
                   narr[i - 1] = narr[i] + val;
               }
           }
      

5. 이분탐색이 끝나면 결과 출력을 위해 구한 l값을 이용하여 정답은 수열을 구하고 출력한다.

소스

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

int n, t, arr[100000], narr[100000];

bool isRight(int val) {
	long long int cnt = 0;
	memcpy(narr, arr, sizeof(int) * n);
	
	for (int i = 1; i < n; ++i) {
		if (narr[i - 1] + val < narr[i]) {
			cnt += narr[i] - (narr[i - 1] + val);
			narr[i] = arr[i - 1] + val;
		}
	}

	for (int i = n - 1; i > 0; --i) {
		if (narr[i] + val < narr[i - 1]) {
			cnt += narr[i - 1] - (narr[i] + val);
			narr[i - 1] = narr[i] + val;
		}
	}

	return cnt <= t;
}

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

	int l = 0, r = 0;

	cin >> n >> t;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
		r = max(r, arr[i]);
	}

	while (l <= r) {
		int mid = (l + r) / 2;
		if (isRight(mid)) {
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}

	for (int i = 1; i < n; ++i) {
		if (arr[i - 1] + l < arr[i]) {
			arr[i] = arr[i - 1] + l;
		}
	}

	for (int i = n - 1; i > 0; --i) {
		if (arr[i] + l < arr[i - 1]) {
			arr[i - 1] = arr[i] + l;
		}
	}
	for (int i = 0; i < n; ++i)
		cout << arr[i] << ' ';
	return 0;
}