백준 3090번 차이를 최소로 문제 풀이

백준저지 3090번 문제 '차이를 최소로' 문제 풀이입니다.

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

인접한 수의 최대 차이값을 c라고 할때, 이 c를 최소로 만들어야 한다.

최대값의 최소값을 바로 구하기는 힘드므로 문제를 조금 변형한다.

인접한 수의 최대 차이값을 최소로 하는 값은 무엇인가 => '인접한 수의 최대 차이값을 c 값으로 만들 수 있는가(Y/N)'

또한 만약 최대 차이값을 c값으로 만들 수 있다면, c+1 으로도 물론 만들 수 있을 것이다. 이러한 특성을 이용하여

바이너리 서치로 문제를 해결할 수 있다.

 
#include <bits/stdc++.h>
using namespace std;

#define MN 100005
int n, T;
int a[MN];
int L[MN], R[MN];
bool ok(int v) {
    R[0]=a[0];
    L[n-1]=a[n-1];
    for (int i=1;i<n;i++) R[i] = min(R[i-1]+v, a[i]);
    for (int i=n-2;i>=0;i--) L[i] = min(L[i+1]+v, a[i]);
    long long inv = 0;
    for (int i=0;i<n;i++) inv += a[i] - min(L[i],R[i]);
    return inv <= T;
}
void ans(int v) {
    R[0]=a[0];
    L[n-1]=a[n-1];
    for (int i=1;i<n;i++) R[i] = min(R[i-1]+v, a[i]);
    for (int i=n-2;i>=0;i--) L[i] = min(L[i+1]+v, a[i]);
    for (int i=0;i<n;i++) {
        int s = a[i]-min(L[i],R[i]);
        printf("%d ", a[i] - s);
    }
}
int main() {
    cin >> n >> T;
    for (int i=0; i < n; i++) {
        scanf("%d", a+i);
    }
    int l = 0, r = MN;
    while (l < r) {
        int m = (l + r) / 2;
        if (ok(m)) r = m;
        else l = m + 1;
    }
    ans(r);
}

ok 함수에서 인접 수 차이 최대값이 v이도록, T번의 감소 연산으로 가능한지 여부를 리턴해준다.

main문의 while문에서 바이너리 서치를 수행하고, 인접수 차이 최대값의 최소값이 r이 되므로,

해당 값이 되도록 감소시킨 배열 값을 ans함수에서 출력해준다.

이제 여기서 T번의 감소 연산으로 가능한지 여부는 O(N)로 체크를 한다.

어차피 감소하는 연산만 가능하므로, 인접 수 차이가 c값이 되도록, 상한선을 R[i] + c 로 정하고, 다음 값이 그 값보다 작으면 그 작의 상한선이 더 낮을 예정이므로 최소값을 취하면서 좌우로 상한선을 체크한다.

더 낮은 상한선을 기준으로 그 값을 초과하는 것들을 다 감소시켜야 한다. 그 감소시켜야 하는 값들이 T 개수 보다 많다면 불가능하다.