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

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

 

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

[탐색] Parametric Search 

[탐색] Parametric Search

인접한 수의 최대 차이의 최대값이 최소가 되도록 접근할 때, Parametric Search 관점으로 접근

인접한 두 수의 최대 차이를 mid 라고 두고, mid를 맞추기 위해서 필요한 연산횟수를 구합니다.

- 연산횟수가 주어진 횟수보다 많이 필요하면 mid 값을 크게해서 재시도 (상한값 ↑)

- 연산횟수 주어진 횟수내에서 처리된다면 mid를 낮춰서 재시도 (상한값 ↓)

(※ 배열을 탐색할 때, 이분탐색을 이용했다면, 최적의 기준값을 찾기 위해 이분탐색을 한다고 보면 됩니다.)

arr = {4, 2, 3, 7, 6} 에서 좌우 간격간(인접한 두 수) 차이 = 1

① 첫번째 원소부터 시작해서 오른쪽을 기준으로 좌측에 있는 수와 차이 비교

    차이가 기준(mid)보다 클 시 우측 숫자에 연산적용

    (4, 2) 비교 → 2 - 4 = -2 ≤ 1(mid) → { 4, 2, 3, 7, 6 }

    (2, 3) 비교 → 3 - 2 = 1 ≤ 1(mid) → { 4, 2, 3, 7, 6 }

    (3, 7) 비교 → 7 - 3 = 4 > 1(mid) → 연산 3회 → { 4, 2, 3, 4, 6 }

    (4, 6) 비교 → 6 - 4 = 2 > 1(mid) → 연산 1회 → { 4, 2, 3, 4, 5 }

    ▶ 현재까지 총 연산 횟수 = 4회

 

② 마지막 원소부터 왼쪽을 기준으로 우측에 있는 수와 차이 비교

    차이가 기준(mid)보다 클 시 좌측 숫자에 연산적용

    → 현재 arr = { 4, 2, 3, 4, 5 }

    (4, 5) 비교 → 4 - 5 = -1 ≤ mid → { 4, 2, 3, 4, 5 } 

    (3, 4) 비교 → 3 - 4 = -1 ≤ mid →  { 4, 2, 3, 4, 5 } 

    (2, 3) 비교 → 2 - 3 = -1 ≤ mid → { 4, 2, 3, 4, 5 } 

    (4, 2) 비교 → 4 - 2 = 2 > mid → 연산 1회 → { 3, 2, 3, 4, 5 } 

    ▶ 현재까지 총 연산 횟수 = 5회

* 해당문제는 중간에 데이터 변경이 있었는데,

   int 범위를 넘어가기에 long long 처리를 해주어야 "100점" 맞을 수 있다.

---

#include <iostream>
#include <algorithm>

using namespace std;

#define LL long long
const int MAX_N = 1e5 + 2;

LL oprCnt;
int N, T;
int arr[MAX_N], copyArr[MAX_N];

bool isPossible(int mid) {
    oprCnt = 0;
    for (int i = 0; i < N; i++)
        copyArr[i] = arr[i];

    for (int i = 0; i < N - 1; i++) {
        if (copyArr[i + 1] - copyArr[i] > mid) {
            oprCnt += copyArr[i + 1] - (copyArr[i] + mid);
            copyArr[i + 1] = copyArr[i] + mid;
        }
    }

    for (int i = N - 1; i > 0; i--) {
        if (copyArr[i - 1] - copyArr[i] > mid) {
            oprCnt += copyArr[i - 1] - (copyArr[i] + mid);
            copyArr[i - 1] = copyArr[i] + mid;
        }
    }
    // 연산 적용횟수 횟수가 T 이하인가 체크
    return oprCnt <= T ? true : false;
}

void printAnsArr(int mid) {
    for (int i = 0; i < N - 1; i++)
        if (arr[i + 1] - arr[i] > mid)
            arr[i + 1] = arr[i] + mid;

    for (int i = N - 1; i > 0; i--)
        if (arr[i - 1] - arr[i] > mid)
            arr[i - 1] = arr[i] + mid;

    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
}

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

    cin >> N >> T;
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    int left = 0, right = 1e9;
    while (left < right) {
        int mid = (left + right) / 2;
        if (isPossible(mid))
            right = mid;
        else
            left = mid + 1;
    }

    // 찾은 기준값으로 배열 갱신 후 정답 출력
    printAnsArr(right);
}