백준 10819 차이를 최대로

사용언어

Visual studio 2019 C++

next_permutation 함수를 통해 순열 구하기

• C++의 STL 사용 ( #include <algorithm> )

함수

함수에 벡터 or 배열 의 주소를 넣으면 된다.

• next_permutation: 현재 나와있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면 (다음에 나온 순열이 순서상 이전 순열보다 작다면 false를 반환

설명만 봐서는 이해가 안될 수 있으니 기초코드로 확인해보자!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {

	vector<int> v(4); 
	for (int i = 0; i < 4; i++) {
		v[i] = i + 1; 
	} 
	// 1 2 3 4
	
	do {
		for (int i = 0; i < 4; i++) {
			cout << v[i] << " ";
		}
		cout << '\n';
	} while (next_permutation(v.begin(), v.end()));
	return 0;
}

1 2 3 4
1 2 4 3
1 3 2 4
    ...
4 3 1 2
4 3 2 1

이런식으로 출력된다. 문제에 사용해보면

[10819 풀이]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	vector<int> v;

	cin >> N;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		v.push_back(a);
	}
	int result = 0;
	sort(v.begin(), v.end());
	do {
		int t = 0;
		for (int i = 0; i < v.size() - 1; i++)
			t += abs(v[i] - v[i + 1]);

		result = max(result, t);
	} while (next_permutation(v.begin(), v.end()));

	cout << result << "\n";
}

next_permutation 함수를 사용해 문제를 손쉽게 해결할 수 있다