백준 10819 차이를 최대로 (c++) : 피너클

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

10819번: 차이를 최대로

백트래킹 문제다.

cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
memset(visited, false, sizeof(visited));
int ans = solve(vector<int>());
cout << ans << '\n';

n을 입력받고 값들을 입력받은뒤 visited를 초기화한다.

그후 ans에 solve함수를 돌려 답을 넣고 출력하면 된다.

int solve(vector<int> v) {
	if (v.size() == n) {
		int ans = 0;
		for (int i = 0; i < n-1; i++) ans += abs(v[i] - v[i + 1]);
		return ans;
	}

solve함수다. v는 무작위로 섞인 배열이 담겨있다.

만약 v의 크기가 n과 같다면 모든 계산을 한뒤 ans를 반환한다.

	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			v.push_back(arr[i]);
			ans = max(ans, solve(v));
			v.pop_back();
			visited[i] = false;
		}
	}
	return ans;
}

아니라면 배열을 섞어야한다. int ans를 준비해준다.

0부터 n까지를 돌며 만약 아직 방문하지 않았다면 

v에 넣고 solve를 돌린뒤 다시 빼준다. 그후 ans를 반환해준다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int n;
int arr[9];
bool visited[9];

int solve(vector<int> v) {
	if (v.size() == n) {
		int ans = 0;
		for (int i = 0; i < n-1; i++) ans += abs(v[i] - v[i + 1]);
		return ans;
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			visited[i] = true;
			v.push_back(arr[i]);
			ans = max(ans, solve(v));
			v.pop_back();
			visited[i] = false;
		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	memset(visited, false, sizeof(visited));
	int ans = solve(vector<int>());
	cout << ans << '\n';
}

전체코드다.