[순열] 10819 차이를 최대로

차이를 최대로 10819

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 10819 차이를 최대로

int n;
int arr[8];

int arrSum(){
	int sum = 0;
	for(int i = 1; i < n; i++){
		sum += abs(arr[i] - arr[i - 1]);
	}
	return sum;
}

int solve(){
	int ans = -123456789;
	
	do{
		int nowSum = 0;
		nowSum = arrSum();
		ans = ans < nowSum ? nowSum : ans;
	}while(next_permutation(arr, arr + n));
	
	return ans;
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n;
	for(int i = 0; i < n; i++) cin >> arr[i];
	
	sort(arr, arr + n);
	
	cout << solve() << '\n';
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

1. 경우의 수 계산

- 모든 순열을 만드는 시간 복잡도는 O(N * N!) 이다. 최대 N 이 8이므로, 8 * 8! = 322,560  브루트 포스가 가능하다.

2. 브루트 포스 구현

- 모든 순열을 만들고 그에 해당하는 모든 합을 구한다.

- next_permutation 의 사용에 대해 익혀두자.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점