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

 

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

KEY

• 다른 유형과 별 다를 거 없는 간단한 백트래킹 문제이다. 
• 그리디로 풀 수 있는지 계속 보다가, 마땅히 떠오르지 않아서 완전탐색을 하기로 결정했다.
• DFS재귀함수를 이용한 방법, <algorithm>헤더가 지원하는 next_permutation메서드를 사용한 방법 두가지로 풀이했다.

 

next_permutation을 이용한 방법

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n;
vector<int> arr;
int answer;
 
void combi(vector<int> v) {
    do {
        int sum = 0;
        for (int i = 0; i < v.size(); i++) { //조합이 완성되면 sum 계산
            if (i == v.size() - 1)
                continue;
            sum += abs(v[i] - v[i + 1]);
        }
        answer = max(answer, sum);
 
    } while (next_permutation(v.begin(), v.end()));
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        arr.push_back(num);
    }
    sort(arr.begin(),arr.end());
    combi(arr);
    cout << answer;
}

 

 

백트래킹을 이용한 방법

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 9;
int n;
int arr[MAX];
vector<int> v;
bool visited[MAX];
int answer;
 
void dfs(int cnt) {
    if (v.size() == n) { //배열의 크기가 n이 됐다면 sum 계산
        int sum = 0;
        for (int i = 0; i < v.size(); i++) {
            if (i == v.size() - 1)
                continue;
            sum += abs(v[i] - v[i + 1]);
        }
        answer = max(answer, sum);
    }
 
    for (int i = 0; i < n; i++) {
        if (visited[i])
            continue;
        visited[i] = true;
        v.push_back(arr[i]);
 
        dfs(cnt + 1);
 
        visited[i] = false;
        v.pop_back();
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    dfs(0);
    cout << answer;
}