본문 바로가기

Programming/BOJ

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)




참고



태그

  • scarletbreez 2019.08.10 23:23 댓글주소 수정/삭제 댓글쓰기

    매번 잘보고 있습니다~ 덕분에 정말 많은 도움을 받고 있습니다.
    혹시 파이썬에서 입력 받음과 동시에 정렬을 해주는 이유가 무엇일까요 ?
    속도향상 측면인지 궁금합니다