백준10819 - 차이를 최대로

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

10819번: 차이를 최대로

순열을 이용하여 푼 문제이다. 숫자는 최대 8개가 들어가기 때문에 시간초과 걱정은 하지 않았다. 숫자를 뽑은 순서에 따라서 결과가 달라지기 때문에 순열을 이용해야 한다. n개 만큼 숫자를 뽑았다면 인접한 수들의 차이를 구하여 절댓값을 취한 뒤 모두 더한다. 그러한 결과들 중에서 가장 큰 결과를 고르면 된다.

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

int n; //입력 받을 숫자들의 갯수
int num; //각각의 숫자로 입력받을 원소
int big = -1; //가장 큰 결과
vector<int> v; //처음 숫자들을 저장할 공간
vector<int> res; //숫자를 뽑은 결과
vector<bool> visit; //숫자를 방문한 여부

//permutation 구현
void dfs(int y) { //y는 현재까지 뽑은 수의 갯수
	if (y == n) {
		int cnt = 0;
		//인접한 두 수의 차이를 구함
		for (int i = 0; i < res.size() - 1; i++) { 
			cnt = abs(res[i] - res[i + 1]) + cnt; 
		}
		big = max(big, cnt); //큰 쪽 선택
		return;
	}
	else {
		for (int i = 0; i < n; i++) { //순서가 다르면 다른 순열이므로 0부터 n까지 탐색
			if (!visit[i]) { //선택하지 않은 원소이면
				res.push_back(v[i]); //원소를 삽입하고
				visit[i] = true; //방문처리한 다음
				dfs(y + 1); //선택한 갯수를 늘려서 다음 탐색으로 수행
				res.pop_back(); //선택한 원소를 삭제하고
				visit[i] = false; //선택한 원소를 미방문 처리
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
		visit.push_back(false);
	}

	dfs(0); //탐색 시작, 처음 뽑은 원소는 0개

	cout << big;
}