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

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

10819번: 차이를 최대로

이번 포스트는 백준 문제의 브루트포스 문제 중 하나인 '차이를 최대로'의 문제와 풀이법을 포스팅하려고 합니다.

 

먼저 문제는 

 

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. 

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

 

입력 : 첫 째줄 N (3 <= N <= 8) 둘 째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

 

출력 : 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

 

 

풀이

이 문제를 딱 보자마자 인덱스가 중복되지 않으면서 순서를 고려하면서 푸는 단순히 나열하는 문제라고 생각했습니다.

 

따라서, 조합을 구하는 코드에다가 약간 변경하여 중복되지 않는 단순 나열 문제로 풀어보았습니다.

이 문제는 모든 경우수를 구해야하기 때문에 브루트포스 문제이며, N의 제한도 8로써 아주 많은 계산을 해야함을 알 수 있습니다.

 

기존의 조합 문제를 풀때 코드를 

void go(int start, int depth) {

	if (depth == n) {


		// 계산하기

		return;
	}


	for (int i = start; i < n; i++) {
		
		selected[depth] = a[i];
		go(i +1, depth + 1);
		
	}


	
}
void solution() {

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> a[i];

	}

	go(0, 0);


	print_selcted();
	

}

 

위의 코드와 같이 start와 depth 파라미터를 사용하여 4C3이라고 하면 depth는 3을 말합니다. 4개 중에 선택한 3개 즉, 깊이를 말하고, start는 수열을 중복되지 않게 선택하기 위해, start부터 시작하여 선택하도록 했습니다. 예를 들어, 1, 2, 3을 3C2 로 위 코드로 작성하면 (1 , 2), (1, 3), (2, 3) 이 위의 논리와 같게 순서대로 프린트 될것입니다. 

하지만 여기서는 (1, 2)와 (2, 1)을 같은 경우수라고 생각하기 때문에 우리가 이 문제에서는 어울리는 해결방법은 아닙니다. 위의 코드를 약간만 변경하도록하겠습니다.

void go(int depth) {

	if (depth == n) {


		cal_max();

		return;
	}


	for (int i = 0; i < n; i++) {

		if (check[i]) continue;

		check[i] = true;
		selected[depth] = a[i];
		go(depth + 1);
		check[i] = false;
	}


	
}
void solution() {

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> a[i];

	}

	go(0);


	cout << result << '\n';
	

}

위의 코드는 start 파라미터를 없애고 대신 한 경우의 수에 똑같은 수가 삽입되지 않도록 check배열을 만들었습니다. check 체크해서 한 경우의 수를 구할 때, 사용하지 않은 수를 선택하도록 만들었습니다.

위와 같은 논리로 1, 2, 3을 3가지 수를 선택하게 된다면, (1, 2, 3), (1, 3 ,2), (2, 1, 3), (2, 3, 2), (3, 1, 2), (3, 2, 1) 결과 값이 나올 것입니다. 이 논리는 이 문제에서 요구하는 논리입니다.

 

따라서, 위의 경우수를 구할 수 있다면 모든 경우수를 구한다음, |[A[0] - A[1]| + |[A[1] - A[2]| + .... + |[A[N-1] - A[N-1]| 식에 대입만 하면 됩니다.

식에 절대값이 씌우져있기 때문에 abs() 수학 함수를 사용하여 구하시면 됩니다.

 

 

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

#define input_max 8 + 1
int n;

int a[input_max];
int selected[input_max];
bool check[input_max];

int result;


void cal_max() {

	int sum = 0;

	for (int i = 0; i < n - 1; i++) {

		sum += abs(selected[i] - selected[i + 1]);
	}

	result = max(sum, result);
}

void go(int depth) {

	if (depth == n) {


		cal_max();

		return;
	}


	for (int i = 0; i < n; i++) {

		if (check[i]) continue;

		check[i] = true;
		selected[depth] = a[i];
		go(depth + 1);
		check[i] = false;
	}


	
}
void solution() {

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> a[i];

	}

	go(0);


	cout << result << '\n';
	

}

int main() {


	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solution();

	return 0;
}