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

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

10819번: 차이를 최대로

 

이 문제는 배열을 입력 받아 순서를 적절히 바꿔 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 값을 최대로 만드는 것이었다. 처음에는 DP문제인줄 알았으나 해결방법이 떠오르지 않았다. 생각을 해보니 N이 최대 8이기 때문에 완전 탐색, 즉 브루트포스로 구현이 가능할 것 같았다.

 

백트래킹을 통해 주어진 배열로 만들수 있는 모든 케이스에 대한 각 결과값을 계산하였고, 최대 결과값을 계속해서 갱신해나가는 방법을 이용하였다. 

 

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

int N;
int n[9];
int result;
vector<int> v;
int visit[9];
int cnt = 0;

void solve() { //브루트포스 
	if (v.size() == N) {
		int tmp = 0;
		for (int i = 0; i < N-1; i++) {
			tmp += abs(v[i + 1] - v[i]);
		}
		result = max(result, tmp);
		return;
	}
	for (int i = 1; i <= N; i++) { //백트래킹
		if (!visit[i]) {
			visit[i] = 1;
			v.push_back(n[i]);
			solve();
			v.pop_back();
			visit[i] = 0;
		}
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> n[i];
	}

	solve();
	cout << result << endl;
}