[Baekjoon Online Judge] 백준 3090번 차이를 최소로(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 3090번 차이를 최소로

(C++, Python)

(글쓴날 : 2020.04.12)

 

---

* Baekjoon Online Judge, 백준 3090번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 3090번 차이를 최소로

---

1) 문제

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

3090번: 차이를 최소로

---

2) 풀이 과정

N개의 정수로 이루어진 배열이 주어지고 최대 T번 배열의 숫자를 1씩 감소시킬 때, 인접한 수들의 차이의 최댓값이 최소가 되는 배열의 값들을 구하는 문제입니다.

 

저의 경우, 이분 탐색을 적용하여 문제에 접근하였으며, C++과 Python을 사용했습니다.

이분 탐색의 mid 값을 인접한 수들의 차이의 최댓값으로 설정하였고, T번안에 해당 차이만큼의 배열을 만들 수 있는지를 조사하는 investigate() 함수를 만들었습니다.

investigate() 함수에서는 두 번의 반복문으로 배열의 값을 감소시키는데, 첫 번째 반복문의 경우, → 방향으로 현재 인덱스의 오른쪽 수를 대상으로 하여 인자로 넘겨받은 차이만큼 감소시키고, 두 번째 반목문의 경우, ← 방향으로 현재 인덱스의 왼쪽 수를 대상으로 하여 똑같이 인자로 받은 차이만큼 감소시킵니다.

두 반복문에서 감소 연산이 발생할 때마다 operCount 변수에 감소시킨 횟수를 저장하였고, 반복문 종료 후 T와 비교하여 해당 차이만큼 배열을 만들 수 있는지 판단하는 과정을 반복하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
int N, T;
vector<int> arr, tempArr, result;
 
bool investigate(int gap)
{
    tempArr.clear();
    tempArr.resize(N, 0);
    copy(arr.begin(), arr.end(), tempArr.begin());
    int operCount = 0;
 
    for (int i = 0; i < N - 1; i++)
    {
        if (tempArr[i + 1] - tempArr[i] > gap)
        {
            operCount += tempArr[i + 1] - (tempArr[i] + gap);
            tempArr[i + 1] = tempArr[i] + gap;
        }
    }
 
    for (int i = N - 1; i > 0; i--)
    {
        if (tempArr[i - 1] - tempArr[i] > gap)
        {
            operCount += tempArr[i - 1] - (tempArr[i] + gap);
            tempArr[i - 1] = tempArr[i] + gap;
        }
    }
 
    if (operCount <= T)
        return true;
    return false;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N >> T;
    arr.resize(N, 0);
    result.resize(N, 0);
 
    for (int i = 0; i < N; i++)
        cin >> arr[i];
 
    int left = 0;
    int right = 1000000000;
    int mid = 0;
 
    while (left <= right)
    {
        mid = (left + right) / 2;
 
        if (investigate(mid))
        {
            copy(tempArr.begin(), tempArr.end(), result.begin());
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
 
    for (int i = 0; i < N; i++)
        cout << result[i] << " ";
 
    return 0;
}

---

* Python 코드

import sys, copy
input = sys.stdin.readline
 
N, T = map(int, input().split())
arr = list(map(int, input().split()))
 
 
def investigate(gap):
    global tempArr
    tempArr = copy.deepcopy(arr)
    operCount = 0
 
    for i in range(N - 1):
        if tempArr[i + 1] - tempArr[i] > gap:
            operCount += tempArr[i + 1] - (tempArr[i] + gap)
            tempArr[i + 1] = tempArr[i] + gap
    
    for i in range(N - 1, 0, -1):
        if tempArr[i - 1] - tempArr[i] > gap:
            operCount += tempArr[i - 1] - (tempArr[i] + gap)
            tempArr[i - 1] = tempArr[i] + gap
    
    if operCount <= T:
        return True
    return False
 
 
left = 0
right = 1000000000
result = []
 
while left <= right:
    mid = (left + right) // 2
 
    if investigate(mid):
        result = copy.deepcopy(tempArr)
        right = mid - 1
    else:
        left = mid + 1
 
print(*result)

---