[ BOJ 백준 3090번 - 차이를 최소로 ] 해설 및 코드

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

목적

자연수 N개로 이루어진 배열 A에서, 감소시키는 연산을 최대 T번 할때, 인접한 수의 차이의 최댓값을 최소로 만들자.

 

접근법

1. 0부터 10^9까지의 범위에서 이분탐색으로 인접한 수의 차이 값의 상한을 구해나간다.

 

2. 상한값을 정했다면, 인접한 두 수의 차이를 상한값 이하로 만들어줘야한다. 여기서 중요한 점은

 행렬을 정방향, 역방향으로 한번씩 순회하면서, 진행 방향으로 나보다 큰 앞 놈만 쳐내야 한다. 

(정방향으로 진행하던 도중에 나보다 큰 뒷 놈이 신경쓰여 역방향으로 쳐내며 진행하다보면 시간초과를 경험할 것이다.)

 

 

#include<iostream>
#define f(i,l,r) for(int i=l;i<r;++i)
#define fr(i,l,r) for(int i=l-1;i>=r;--i)
using namespace std;
 
const int LEN = 1e5 + 1;
int n, t, a[LEN], b[LEN];
 
bool minimize(int lim) {
    f(i, 0, n)b[i] = a[i];
 
    int cnt = t;
    f(i, 1, n) if (b[i] - b[i - 1] > lim) {
        int tmp = b[i - 1] + lim;
        cnt -= (b[i] - tmp);
        if (cnt < 0)return false;
        b[i] = tmp;
    }
    fr(i, n - 1, 0) if (b[i] - b[i + 1] > lim) {
        int tmp = b[i + 1] + lim;
        cnt -= (b[i] - tmp);
        if (cnt < 0)return false;
        b[i] = tmp;
    }
 
    return true;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> t;
    f(i, 0, n) cin >> a[i];
 
    int l = 0, r = 1e9;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (minimize(mid))r = mid - 1;
        else l = mid + 1;
    }
    minimize(l);
    f(i, 0, n)cout << b[i] << ' ';
}

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.