BOJ 10819 · 차이를 최대로

알고리즘 분류 : 브루트 포스  

|A[i]-A[i-1]|를 0부터 N-1까지 모두 더했을 때, 가장 큰 값을 찾는 문제다. A 리스트의 값은 순서가 바뀔 수 있으므로, 순열로 하나씩 순서대로 구해보면 된다. 절댓값은 abs 함수를 이용하면 된다.

• A 값을 입력받은 후, 정렬한다.
• A 값을 next_permutation(C++ STL) / permutations(Python itertools)을 통해 순열을 돌린다.
• 합을 구해서 최댓값이면 저장한다.

---

C++ 소스코드

#include <cstdio>
#include <algorithm>
using namespace std;

int solve(int n) {
    int a[n];
    int ans = 0;
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    do {
        int sum = 0;
        for (int i=0; i<n-1; i++) {
            sum += abs(a[i]-a[i+1]);
        }
        if (ans < sum) ans = sum;
    } while (next_permutation(a, a+n));
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solve(n));
    return 0;
}

---

Python 3 소스코드

from itertools import permutations
n = int(input())
a = permutations(sorted(list(map(int, input().split()))))
ans = 0
for k in a:
    sums = 0
    for i in range(n-1):
        sums += abs(k[i]-k[i+1])
    ans = max(ans, sums)
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 10819
• 다음 순열