BOJ 10819번 차이를 최대로

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

github : https://github.com/junho0956/Algorithm/blob/master/10819/10819/%EC%86%8C%EC%8A%A4.cpp

 

완전탐색으로 가능한 모든 경우를 탐색하였으며

범위가 작아서 그런지 빠른 시간내로 해결했습니다.

탐색간 배열을 계속 만들어주어서 수를 확인하고 수가 없다면 삽입 후 넘기는 방식으로 코드하였습니다.

 

next_permutation (조합) 으로 구할 수 있지만 

아직 사용법과 내부 구현을 몰라서 공부 후에 적용해보겠습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
 
int arr[8];
int p[101];
int m[101];
int N, Max;
 
void ans(int v[], int index) {
    
    int vv[8];
    for (int i = 0; i < index; i++) vv[i] = v[i];
 
    if (index == N) {
        int total = 0;
        for (int i = 0; i < N - 1; i++) total += abs(vv[i] - vv[i + 1]);
 
        Max = max(Max, total);
        return;
    }
 
    for (int i = 0; i < N; i++) {
        int cnt = 0;
        for (int k = 0; k < index; k++) {
            if (vv[k] == arr[i]) cnt++;
        }
        if (arr[i] == 0 || arr[i] > 0) {
            if (cnt != p[arr[i]]) {
                vv[index] = arr[i];
                ans(vv, index + 1);
            }
        }
        else {
            if (cnt != m[arr[i]*-1]) {
                vv[index] = arr[i];
                ans(vv, index + 1);
            }
        }
    }
}
 
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        if (arr[i] == 0) p[0]++;
        else if (arr[i] > 0) p[arr[i]]++;
        else m[arr[i]*-1]++;
    }
 
    for (int i = 0; i < N; i++) {
        int v[8];
        ans(v, 0);
    }
 
    cout << Max;
    return 0;
}