백준 10819 (차이를 최대로)

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

10819번: 차이를 최대로

해당 문제는 N개의 정수가 주어질 때 해당 정수를 아래에 식에 맞춰 계산 했을 때 나올 수 있는 최대한의 수를 구하는 문제이다. 이때 주어진 정수의 위치는 사용자가 바꿀 수 있으므로 순열을 이용하여 주어진 정수들의 숫자를 바꾸어 모든 탐색을 진행한다. 이렇게 탐색을 진행하면서 바꾼 수열에 식을 대입하여 결과 값만 비교하면 풀리는 문제이다.

 

풀이 :

#include <iostream>
#include <vector>


using namespace std;

int n, maxx = -9999999;
vector<int> nList;
vector<int> results;
int used[10001];

// 순열 합계구하기
int getSum(vector<int> nList){
	int sum = 0;
	for (int i = 0; i < n - 1; ++i){
		sum += abs(nList[i] - nList[i + 1]);
	}
	return sum;
}

void dfs(int level){

	if (level == n){
		int sum = getSum(results);
		if (maxx < sum) maxx = sum;
		return;
	}

	for (int i = 0; i < n; ++i){
		if (used[i] == 1) continue;
		used[i] = 1;
		results.push_back(nList[i]);
		dfs(level + 1);
		used[i] = 0;
		results.pop_back();
	}

}


int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;
	for (int i = 0; i < n; ++i){
		int tmp;
		cin >> tmp;
		nList.push_back(tmp);
	}
	dfs(0);
	cout << maxx << endl;
}