BOJ 3090 차이를 최소로

문제

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

주어진 배열의 수들을 t번 감소시킬 수 있을 때 인접한 숫자의 차이의 최댓값을 최소화 하는 문제이다.

 

풀이

나한테는 많이 어려웠던 문제였다.

지금까지 코드포스에서도 한번쯤은 봤던 문제긴 한데, 파라마트릭 서치라는 생각을 전혀 하지 못했던 것 같다.

 

이 문제가 파라마트릭 서치라는 생각을 했어야 되는 이유

1. "최적화" 문제이다. 한번쯤은 생각해 봐야지?

2. "이때, 인접한 숫자의 차이의 최댓값을 최소로 하는 프로그램을 출력하시오." 

    "최대값을 최소로", "최솟값을 최대로" 문제이다.

 

자 이제 파라마트릭 서치로 인접한 숫자 사이의 간격이 diff 이하여야 한다고 구했다고 하자.

과연 그런 해가 존재하는지 결정함수를 어떻게 짜야 할까?

 

답은 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 쑥 훑고 가면 된다.

왼쪽에서 a, b가 있을 때 a+diff<b 라면 b는 a+diff 로 바꾸는 것이 최적해이고, 이렇게 갱신된 b로 다음 계산을 할 수 있다.

솔직히 나는 이 생각을 하지 못했다. 꽤 재밌는 문제였으니 외워 두도록 하자.

 

또 하나 주의할 점 :

구현을 반열린 구간으로 하니, lo=0 으로 설정해 버리면 실제로 hi는 0보다 커질 수 밖에 없다.

따라서 답이 될 가능성이 있는 구간이 [a, b] 라 하면 lo=a-1, hi=b+1 로 설정하자.

 

시간 복잡도 : $O(Nlog10^9)$

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int n, t, arr[MAXN+10];

bool decide(int diff)
{
    int i;
    int change[MAXN+10];
    for(i=1; i<=n; i++) change[i]=arr[i];

    ll cnt=0;
    for(i=1; i<=n-1; i++) if(change[i]+diff<change[i+1]) { cnt+=change[i+1]-change[i]-diff; change[i+1]=change[i]+diff; }
    for(i=n; i>=2; i--) if(change[i]+diff<change[i-1]) { cnt+=change[i-1]-change[i]-diff; change[i-1]=change[i]+diff; }

    return cnt<=t;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int i, j;

    scanf("%d%d", &n, &t);
    for(i=1; i<=n; i++) scanf("%d", &arr[i]);

    int lo=-1, hi=1e9+10;
    while(lo+1<hi)
    {
        int mid=lo+hi>>1;
        if(decide(mid)) hi=mid;
        else lo=mid;
    }

    for(i=1; i<=n-1; i++) if(arr[i]+hi<arr[i+1]) arr[i+1]=arr[i]+hi;
    for(i=n; i>=2; i--) if(arr[i]+hi<arr[i-1]) arr[i-1]=arr[i]+hi;

    for(i=1; i<=n; i++) printf("%d ", arr[i]);
    return 0;
}