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

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

C++

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

// next_permutation , 총 원소의 개수 입력 오름차순 정렬 후 호출 순열 출력
// do - while 문을 사용해야한다. do에서 값 넣어주고, while에서 재 정렬

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // 최대 8개 되게 작다.
    // 배열에 들어있는 수 순서 적절히 바꿈. C는 중복 제한이라 P를 써야한다고 생각

    int n,final = 0;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr, arr+n);

    // next_permutation 사용해서 모든 경우의 수 구하면서
    // 계속 돌리고 합 구하면서 더 크면 바꿔본다.
    do {
        int sum = 0;
        for(int i = 1; i < n; i++) {
            sum += abs(arr[i] - arr[i-1]);
        }
        final = max(sum, final);
    }while(next_permutation(arr, arr+n));

    cout << final << "\n";
}

문제풀이

• n개의 정수로 만들 수 있는 모든 결과값을 do-while문과 next_permutation함수를 사용해서 구해본다. next_permutation함수를 사용하기전에 sort통해 정렬하고, arr[i] - arr[i-1]의 절댓값을 구하는 것을 반복하면 가장 큰 수를 구한다.

Comment

• next_permutation : 주어진 순열을 사전 순의 다음 순열로 바꾸고 true를 리턴하는 함수
  next_permutation 함수의 첫 번째 인자로는 순열을 구할 대상 시작점의 주소 혹은 iterator를, 두 번째 인자로는 끝나는 지점의 주소 혹은 iterator를 넘겨받는다. 또한 현재 순열이 사전 상에서의 마지막일 경우 true가 아닌 false를 리턴한다. 때문에 첫 번째 실행 후 조건에 따라 구문을 실행하는 do-while문과 연계하여 가능한 모든 순열을 만들 수 있다. 가능한 모든 순열을 얻고 싶을 경우, 오름차순으로 정렬된 초기값을 넘겨 주어야 한다.
  중복이 있는 원소들은 중복을 제외하고 순열을 만들어줍니다.

• next_permutation 함수를 이 문제를 통해 처음 활용해봤다. 직접 함수를 사용하는 것이 아닌 이 STL을 사용해서 모든 경우의 수를 비교할 수 있기 때문에 잘 활용해봐야겠다.

상황	next_permutation 사용 가능 여부	설명
순열 (Permutation)	✅ 직접 사용 가능	모든 순서를 탐색하므로 중복 자동 제거됨
조합 (Combination)	✅ 트릭 사용 시 가능	이진 마스크 또는 정렬된 초기 배열로 중복 방지 가능
중복 허용 조합/순열	❌ 기본 next_permutation으로는 부적절	별도 처리 필요