[백준(BOJ)] 10819번 차이를 최대로 C++

문제 : https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

 

 

어떤 문제인가?

 

배열이 있을 때

| A [0] - A [1] | + | A [1] - A [2] | +... + | A [N-2] - A [N-1] |의 값이 최대가 되게 배열을 재배치해야 한다.

배열을 재배치하고 난 후 얻을 수 있는 최댓값을 출력하면 된다.

 

 

접근 방법

 

숫자를 재배치하기 위해서는 어떤 숫자를 어디에 배치해야 할지를 결정해야 한다.

 

따라서 데이터는 앞, 뒤 삭제 삽입 연산이 간편한 deque를 사용하기로 했다.

deque<int> temp;
deque<int> diff;

 

 

 

int n;

cin >> n;

for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    temp.push_back(a);
}
sort(temp.begin(), temp.end());

diffMax();

덱에 숫자 배열을 입력받아 저장한다. 

 

 

 

나는 이렇게 문제를 풀었다.

20 1 15 8 4 10을 예제 입력처럼 입력했다고 생각하자.

차이를 최대로 하기 위해서는 당연히 가장 작은 수와 가장 큰 수를 옆에 배치해야 한다.

 

따라서 먼저 deque를 sort함수를 사용해 오름차순으로 정렬해준다.

 

그렇다면 1 4 8 10 15 20으로 정렬되어있을 것이다.

 

이제 diffMax함수를 통해 연산을 할 것이다.

 

void diffMax() {

    if (diff.size() == n) {
        return;
    }

    if (diff.empty()) {
        diff.push_back(temp.front());
        temp.pop_front();
        diffMax();
        return;
    }

    int f = max(abs(diff.front() - temp.front()), abs(diff.front() - temp.back()));
    int b = max(abs(diff.back() - temp.front()), abs(diff.back() - temp.back()));

    if (f > b) {
        if (abs(diff.front() - temp.front()) > abs(diff.front() - temp.back())) {
            diff.push_front(temp.front());
            temp.pop_front();
        } else {
            diff.push_front(temp.back());
            temp.pop_back();
        }

    } else {
        if (abs(diff.back() - temp.front()) > abs(diff.back() - temp.back())) {
            diff.push_back(temp.front());
            temp.pop_front();
        } else {
            diff.push_back(temp.back());
            temp.pop_back();
        }
    }

    diffMax();

}

 

입력을 저장한 temp라는 덱에서 diff라는 덱으로 숫자들을 옮겨가는 방식이다.

따라서 재귀를 사용할 것이다.

 

탈출 조건은 diff의 size가 n이 됐을 때이다.

diff의 size가 n이 됐다는 말은 즉 모든 숫자들이 옮겨졌고 재배치가 완료됐다는 뜻이다.

 

처음 diffMax가 호출됐을 때는 diff덱이 비어있을 것이다.

따라서 temp의 가장 작은 값인 front를 diff에 추가해주고

temp에서 pop_front를 해준다.

그다음 diffMax를 호출해 다음 연산을 진행하도록 한다.

 

이제 어떻게 차이가 가장 차이가 큰 수를 정할지 생각해야 한다.

 

먼저 diff덱에 맨 앞에 삽입하는 경우이다.

이때는 temp의 front와 diff의 front의 차이의 절댓값과 temp의 front와 diff의 back의 차이의 절댓값을 비교해

더 큰 수를 f에 저장한다.

또, temp의 front과 diff의 back의 차이의 절댓값과 temp의 back과 diff의 back의 차이의 절댓값을 비교해

더 큰수를 b에 저장한다.

 

이제 f와 b를 비교한다.

f가 더 크다는 것은 f를 diff의 앞에 삽입했을 때 차이가 가장 크게 된다는 것이다.

이때는 temp의 front와 diff의 front의 차이의 절댓값과 temp의 front와 diff의 back의 차이의 절댓값을 비교해 만약 전자가 더 크다면

temp의 front를 diff의 앞에 삽입해주고 temp를 pop_front 해준다.

후자가 더 크다면 반대로 해주면 된다.

 

 

b가 f보다 클 경우는 f가 b보다 클 경우의 정확히 반대로 해주면 된다.

 

이렇게 호출된 모든 diffMax함수가 종료하게 되면 main함수에서 문제에서 요구한 식을 계산하면 된다.

 

int total = 0;

for (int i = 0; i < diff.size() - 1; i++) {
    total += abs(diff[i] - diff[i + 1]);
}
cout << total;

 

 

 

무엇이 어려웠는가?

문제를 읽고나서 패드에 풀이 방법을 적을 때는 술술 적혔다.

머릿속에서는 아주 자연스러운 과정으로 차이가 최대가 되는 방법을 찾을 수 있었다.

하지만 아주 자연스러운 과정을 코드로는 어떻게 표현해야 할까 고민이 됐다.

 

수열의 앞과 뒤를 비교하고 추가하고 삭제하는 과정을 생각하다 deque를 사용하기로 결정했고.

그 뒤로는 조금 복잡한 구현 문제였던 것 같다.

 

 

 

배운 점

문제를 읽고 deque와 재귀가 떠올랐다.

이제 어느정도 쉬운 수준의 문제는 쉽게 풀 수 있어진 것 같다.

쉬운 문제를 쉽게 풀 수 있다는 게 웃기는 말이지만ㅋㅋㅋ.....

적어도 나에게는 그렇다.. 

조금은 실력이 늘은게 느껴져서 문제를 풀 때마다 기분이 좋다.