백준 10819 c++ "차이를 최대로" -PlusUltraCode-

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

 

[필자 사고]

백트래킹 문제를 이용하여 모든 경우의 수를 풀어야 한다.

순서가 중요하므로 for문을 돌 때 idx =0 부터 하게 되면 쉽게 풀 수 있다.

 

다만 이 문제를 처음 마주했을 때 백트래킹 및 브루트포스 알고리즘이라고 생각해내야 되는 사고 과정이 중요하다 느껴진다.

일단 N의 크기가 매우 작다 -> 브루트포스 알고리즘이 가능하다.

이로인해 순서가 중요한 정렬 가능한 모든 경우의 수를 택할 수 있기 때문에 위와 같은 알고리즘을 선택할 근거가 마련이 된다.

 

아래는 자세한 코드해설이다.

[코드 해설]

Input()

• 사용자로부터 정수 N과 N개의 정수를 입력받아 arr 벡터에 저장한다.

calculateResultArr()

• 현재 resultArr에 저장된 순열에 대해 인접한 원소 간의 차이의 절댓값을 모두 더하여 그 합을 반환한다.

Print()

• 현재의 resultArr에 저장된 값을 공백으로 구분하여 출력한다. (현재 로직에서는 호출되지 않음)

DFS(int depth)

• 백트래킹을 통해 arr 배열의 모든 순열을 생성한다.
• depth는 현재까지 선택한 원소의 수를 의미한다.
• depth가 N에 도달하면, 해당 순열에 대한 차이의 합을 계산하고 maxNumber를 갱신한다.
• 방문 여부를 확인하며 중복 없이 순열을 구성한다.

Game_Start()

• visited 벡터를 false로 초기화하고, DFS를 시작한다.
• 최종적으로 구한 최댓값(maxNumber)을 출력한다.

main()

• 전체 실행 흐름을 담당한다.
• 입력을 받고, 게임 로직을 실행한다.

[소스 코드]

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

int N;
vector<int> arr;
vector<int> resultArr;
vector<bool> visited;
int maxNumber = -1;
void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

}

int calculateResultArr() {
	int sum = 0;
	for (int i = 0; i < resultArr.size()-1; i++) {
		sum += abs(resultArr[i] - resultArr[i + 1]);
	}

	return sum;
}
void Print() {
	for (int i = 0; i < N; i++) {
		cout << resultArr[i] << " ";
	}
	cout << '\n';
}

void DFS(int depth) {
	if (depth == N) {
		int sum = calculateResultArr();
		maxNumber = max(maxNumber, sum);
		return;
	}

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

		if (visited[i]==true)continue;
		resultArr.push_back(arr[i]);
		visited[i] = true;
		DFS(depth + 1);
		resultArr.pop_back();
		visited[i] = false;
		
	}

}

void Game_Start() {
	visited.resize(N, false);
	DFS(0);
	cout << maxNumber;
}

int main(void) {
	Input();
	Game_Start();
}