C++ / 백준 / 10819 / 차이를 최대로

문제

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

10819번: 차이를 최대로

문제풀이

두 가지방법으로 문제를 풀었다.

첫번째는 <algorithm>에 있는 모든 순열의 경우의 수를 알려주는 next_permutation 함수를 이용했다.

두번째는 오름차순으로 정렬해서 벡터를 반으로 나누고 계산하고,

내림차순으로 정렬해서 벡터를 반으로 나누고 계산을 해서 큰 값을 출력했다.

 

 

코드

1)

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

int main() {
	int N = 0;
	int idx = 0;
	cin >> N;
	vector<int>arr(N, 0);
	for (idx = 0; idx < N; ++idx)
		cin >> arr[idx];
	sort(arr.begin(), arr.end());

	int answer = 0;
	int sum = 0;
	do {
		sum = 0;
		for (idx = 0; idx < N-1; ++idx)
			sum += abs(arr[idx] - arr[idx + 1]);		
		answer = max(answer, sum);
	}while(next_permutation(arr.begin(), arr.end()));
	cout << answer;
}

 

2)

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

int main() {
	int N = 0;
	int idx = 0;

	cin >> N;

	vector<int>big;
	vector<int>small;
	vector<int>temp(N,0);
	
	int end = 0;
	if (N % 2 == 0)end = N / 2;
	else end = N / 2 + 1;
	int num = 0;
	for (idx = 0; idx < N; ++idx) {
		cin >> temp[idx];
	}
	sort(temp.begin(), temp.end(),greater<>());
	for (idx = 0; idx < end; ++idx) {
		big.push_back(temp[idx]);
	}

	int idx2 = 0;
	for (idx; idx < N; ++idx) {
		small.push_back(temp[idx]);
	}
	
	int sum = abs(small[0]-big[0]);
	for (idx = 1; idx < small.size(); ++idx) {
		sum += abs(small[idx] - big[idx - 1]);
		sum += abs(small[idx] - big[idx]);		
	}

	idx = small.size()-1;
	if (N % 2 == 1) sum += abs(big[idx] - big[idx + 1]);

	big = vector<int>();
	small = vector<int>();
	sort(temp.begin(), temp.end());
	for (idx = 0; idx < end; ++idx) {
		big.push_back(temp[idx]);
	}

	idx2 = 0;
	for (idx; idx < N; ++idx) {
		small.push_back(temp[idx]);
	}	

	int sum2 = abs(small[0] - big[0]);
	for (idx = 1; idx < small.size(); ++idx) {
		sum2 += abs(small[idx] - big[idx - 1]);
		sum2 += abs(small[idx] - big[idx]);
	}
	
	idx = small.size() - 1;
	if (N % 2 == 1) sum2 += abs(big[idx] - big[idx + 1]);

	int answer = max(sum, sum2);
	cout << answer;
}