[C++] 백준 10819번 차이를 최대로

1. 문제이해

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

10819번: 차이를 최대로

 

배열의 원소의 개수(N)와 원소값이 주어진다.

이때, 배열의 배치 순서를 적절히 바꾸어 다음과 같은 연산을 수행했을 때

얻을 수 있는 최댓값을 구하는 것이 목표이다.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

 

 

 

2. 문제풀이

 

문제를 똑바로 읽자..

차이를 최대로 라는 문제 제목과 점화식을 잘못 보고 한참 헤맸다.

문제의 점화식을 잘 봐야 한다.

 

|A[0] - A[1]| + |A[1] - A[2]| + |A[2] - A[3] | + ... + |A[N-2] - A[N-1]|

 

위 점화식을 보면 알 수 있듯, 일정한 원소가 반복되어 더해지거나 빠져야한다.

다행히도, 해당 문제에서의 원소의 범위(N)은 8 이하 이므로, 모든 경우의 수를 다 따져보아도 괜찮다.

 

필자는 모든 경우의 수를 따져보고, 그 중 가장 큰 값을 출력했는데,

해당 과정에서 필요한 함수가 있는데, 바로 next_permutation 이다.

bool next_permutation (arr.begin(), arr.end());

 

next_permutation 함수는, 이름 자체에서 볼 수 있듯이

순열(permutation), 즉, 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 구하는 함수이다.

첫번째 인자가 구하고자 하는 순열의 시작, 두번째 인자가 순열의 끝으로,

 해당 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다.

다음 순열이 없다면, 즉 역순이 된다면, false를 반환하게 된다.

필자는 위 함수를 통해 모든 경우의 수를 따져주었다.

 

 

 

3. 소스코드

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

int main() {
	vector<int> arr;
	int N;
	int element;
	int sum;
	int result = 0;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> element;
		arr.push_back(element);
	}

	// 원소를 오름차순 정렬
	sort(arr.begin(), arr.end());

	// 모든 경우의 수를 다 탐색
	while (next_permutation(arr.begin(), arr.end())) {
		sum = 0;
		for (int i = 0; i < arr.size() - 1; i++) {
			sum += abs(arr[i] - arr[i + 1]);
		}
		// 기존 result 값과 비교하여 더 큰값을 채택
		result = max(result, sum);
	}

	cout << result;

	return 0;
}

먼저 원소의 개수(N)와 각 원소들을 입력받고, 입력받은 원소들을 오름차순으로 정렬한다.

(아래 모든 경우의 수 를 탐색하기 위해 오름차순 정렬)

이후, 2. 문제풀이에서 이야기 한 next_permutation 함수를 통해

모든 경우의 수를 탐색,해당 경우의 수마다 점화식을 수행하고, sum 에 값을 저장한다.

이후 sum 값과 result 값을 비교하여, 더 큰 값을 result 값으로 채택한다.

위와 같은 과정을 반복하면, result 값에 모든 경우의 수들 중 가장 큰 값이 남게 된다.

 

 

---

문제를..... 제대로... 읽자....🤦‍♂️

쉬운 줄 알고 덤볐다가 아니었던 문제였다..

그래도 내장 함수를 이용하면 간단하게 풀 수 있었다.

저번에 JLPT 1회차 때 N3 합격 수기를 쓰려고 했다가,

 N3은 합격 수기를 쓰기에는 좀 그런가 싶어서 안썼었는데,

이번 2회차에 JLPT N2도 합격했는데, 해당 합격수기와 함께 오도록 하겠습니당💪

 

문제에 대한 지적이나 질문은 항상 감사하게 받고있습니다.😌