[C++백준] 실버 2/ 10819번 차이를 최대로

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

10819번: 차이를 최대로

#include <iostream>
#include<istream>
#include<algorithm>
#include <string>
 
 
 
using namespace std;
 
static int ans = 0;
static int maxAns = 0;
 
 void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
 void permatuation(int *arr, int depth, int n, int r) {
    
    if (depth == r) {
        ans = 0;
        int i = 0;
        int j = 1;
        while (j <=r-1&&i<=r-2) {
            
            ans += abs(arr[j] - arr[i]);
            i++;
            j++;
        }
        
        if (ans > maxAns) {
            maxAns = ans;
 
        }
        return ;
    }
    else {
        for (int i = depth; i < n; i++) {
            swap(arr[depth], arr[i]);
            permatuation(arr, depth + 1, n, r);
           swap(arr[depth], arr[i]);//다시 되돌려줌
        }
    }
}
 
int main(){
    int n;
    scanf("%d", &n);
    int* arr = new int[n];
    
    
 
    
    for (int i = 0; i < n; i++) {
            int num;
            scanf("%d", &num);
            arr[i] = num;
            
    }
    sort(arr, arr + n);
    permatuation(arr, 0, n, n);
    
    printf("%d", maxAns);
 
        
    return 0;
    
}

이 문제는 규칙을 찾아보려고 부단히 노력했지만 그냥 순열을 통해 숫자들이 나열될 수 있는 경우의 수를 모두 찾아 그 차이가 최대인것을 찾아내면 됐다. 

순열 들어가기 전에 정렬을 해주는 것은 먼저 정렬해주지 않으면 나올 수 있는 경우의 수가 끝까지 나오지 않을 수 있어서 먼저 정렬하고 -> 순열을 찾아주는것이 중요하다. 

 

순열을 구현하는 방법은 두가지가 있는데 첫번째는 재귀+swap이고 두번째는 백트래킹이다. 

 

재귀+swap으로 풀어봤는데  다른 사람의 코드를 참고했기에 아래 첨부해두었다. 재귀를 통해서 계속 반복하는 과정인데 너무 길어서 그냥 코드 자체는 간단하니 외우려 한다..ㅋㅋㅋ 

 

백트래킹

algorithm 헤더에 next_permutation이 포함되어있다. 백트래킹을 쓰지 않은 이유는 순열을 출력할 때는 매우 편리한 것같은데 문제에서는 차이를 최대로 하라는 조건이 있어서 재귀와 swap을 썼다. 

 

순열 참고 사이트

https://ansohxxn.github.io/algorithm/permutation/

(C++) 순열(Permutation) 구현하기