[백준 10819번] 차이를 최대로 풀이

10819번: 차이를 최대로

배열의 크기 N과 요소들이 주어졌을 때, 배열의 순서를 적절히 바꾸어
sum = |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 의 최댓값을 구하는 문제이다.
재귀 함수를 통해 배열의 순서를 정하고, sum의 최댓값을 구하는 방법이 있다. 먼저 원소의 개수 N과 배열 A를 초기화시키자.

 

scanf("%d", &N);
memset(A, 0, sizeof(A));

for (int i=0; i<N; i++)
    scanf("%d", &A[i]);

함수 solve()는 배열의 시작 인덱스를 입력으로 받아 가능한 모든 배열의 조합을 탐색하고 재귀가 끝날 때 sum을 도출하는 함수이다. 입력을 저장했던 배열 A를 기준으로 0부터 N-1 인덱스까지 모두 시작점이 될 수 있다. 따라서 이를 순회하며 solve()를 실행시킨다.

 

for (int i=0; i<N; i++) {
    vector<bool> check(N, false);
    int sum = 0;
    solve(i, check, sum);
}

N = 4 이고 처음 시작점의 인덱스가 0일 때 가능한 모든 조합들을 살펴보면,

 

// element가 4개일 때 가능한 순서
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1

 

시작 인덱스 0 이후 가능한 인덱스는 이미 지나온 0을 제외한 1, 2, 3 중 하나이다. 0과 1을 지났을 때 가능한 인덱스는 이미 지나온 것들을 제외한 2, 3 중 하나이다. 0, 1, 2를 지났을 때 가능한 인덱스는 지나온 것들을 제외하고 3 하나 뿐이다. 함수 solve()는 이렇게 입력되는 인덱스와 이미 지나온 것들을 확인하여 재귀적으로 다음인덱스를 지정한다.

 

void solve(int idx, vector<bool> check, int sum) {

    check[idx] = true;
    for (int i=0; i<N; i++) {
        if (check[i]) continue;
        solve(i, check, sum+max(A[idx]-A[i], A[i]-A[idx]));
    }
    if (re < sum) re = sum;
}

시작 인덱스 idx가 입력되었을 때, 해당 인덱스를 사용했음을 check에 기록한다. i=0 ~ i=N-1 까지 인덱스 중에서 아직 사용하지 않은 인덱스만이 다음 인덱스가 될 수 있으므로 check[i]를 확인한다. 사용하지 않은 인덱스는 다음 인덱스로 지정하고, 이번 인덱스와 다음 인덱스 차의 절댓값을 구해 sum에 더해준다.

인덱스가 모두 사용되고 check의 모든 자리가 true가 되었을 때 재귀는 끝나게 된다. 우리는 sum의 최댓값을 구하는 것이므로 변수 re보다 해당 인덱스까지 구한 합이 더 크면 re에 해당 값을 저장한다. 참고로, A[idx]-A[i] 의 절댓값은 max(A[idx]-A[i], A[i]-A[idx]) 를 통해 구할 수 있다.

모든 시작점을 순환하여 가장 큰 sum을 구하는 전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int N;
int A[8];
int re = -1;

void solve(int idx, vector<bool> check, int sum) {

    check[idx] = true;
    for (int i=0; i<N; i++) {
        if (check[i]) continue;
        solve(i, check, sum+max(A[idx]-A[i], A[i]-A[idx]));
    }
    if (re < sum) re = sum;
}

int main() {

    scanf("%d", &N);
    memset(A, 0, sizeof(A));

    for (int i=0; i<N; i++)
        scanf("%d", &A[i]);

    for (int i=0; i<N; i++) {
        vector<bool> check(N, false);
        int sum = 0;
        solve(i, check, sum);
    }
    printf("%d", re);
    return 0;
}