백준 3090번 차이를 최소로

문제 링크입니다: https://www.acmicpc.net/problem/3090

이분 탐색을 이용해서 풀어야하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 이분 탐색을 진행하며 T번의 변경 안에 모든 인접한 숫자의 차가 mid 이하이면 true 아니라면 false를 반환하는 possible 함수를 구현합니다.

2. 기존에 풀었던 이분 탐색과 다르게 최소 차를 찾는 과정이므로 1번이 성립하면 high를 줄이고 성립하지 않으면 low를 늘립니다.

3. possible 함수가 성립하고 mid가 기존 차보다 작아야 result 배열을 업데이트해줍니다.

#include <iostream>

#include <queue>

using namespace std;

 

const int MAX = 100000 + 1;

 

int N, T;

int A[MAX];

int copyA[MAX];

int result[MAX];

 

bool possible(int diff)

{

        for (int i = 0; i < N; i++)

                 copyA[i] = A[i];

 

        int cnt = 0;

        //인접한 오른쪽 체크

        for (int i = 0; i<N - 1; i++)

                 if (copyA[i + 1] - copyA[i] > diff)

                 {

                         cnt += copyA[i + 1] - (copyA[i] + diff);

                         copyA[i + 1] = copyA[i] + diff;

                 }

        //인접한 왼쪽 체크

        for (int i = N - 1; i > 0; i--)

                 if (copyA[i - 1] - copyA[i] > diff)

                 {

                         cnt += copyA[i - 1] - (copyA[i] + diff);

                         copyA[i - 1] = copyA[i] + diff;

                 }

 

        //변경 횟수가 T 이하인가 체크

        if (cnt <= T)

                 return true;

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> T;

 

        for (int i = 0; i < N; i++)

                 cin >> A[i];

 

        int low = 0, high = 1e9;

        int minDiff = 1e9; //최소 차

        while (low <= high)

        {

                 int mid = (low + high) / 2;

                 if (possible(mid))

                 {

                         for (int i = 0; i < N; i++)

                                 result[i] = copyA[i];

                         high = mid - 1;

                 }

                 else

                         low = mid + 1;

        }

        for (int i = 0; i < N; i++)

                 cout << result[i] << " ";

        cout << "\n";

        return 0;

}

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~