프로그래밍/알고리즘

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)




참고



반응형