[백준 10819] 차이를 최대

문제링크 : https://www.acmicpc.net/problem/10819

💻 문제 풀이 : C++

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr, selected;
int used[10];
int answer;

int my_abs(int a) {
	return a > 0 ? a : a * (-1);
}

int my_max(int a, int b) {
	return a > b ? a : b;
}

int get_calc(vector<int> v)
{
	int ans = 0;
	for (int i = 0; i < v.size() - 1 ; i++)
	{
		ans += my_abs(v[i] - v[i + 1]);
	}
	return ans;
}

void dfs(int depth, int n)
{
	if (depth >= n) {
		/*for (int i = 0; i < n; i++)
			cout << selected[i] << " ";
		cout << endl;*/
		answer = my_max(answer, get_calc(selected));
		get_calc(selected);
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (used[i] == 1) continue;
		selected.push_back(arr[i]);
		used[i] = 1;
		dfs(depth + 1, n);
		selected.pop_back();
		used[i] = 0;
	}
}

int main()
{
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int input;
		cin >> input;
		arr.push_back(input);
	}
	dfs(0, N);
	cout << answer;

	return 0;
}

💻 문제 풀이 : Python

Permutation 라이브러리사용

import sys
from itertools import permutations

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

cases = list(permutations(A))

answer = 0

for case in cases:
    mid_sum = 0
    for i in range(N-1):
        mid_sum += abs(case[i] - case[i+1])
    answer = max(mid_sum, answer)
print(answer)

Backtracking 사용

import sys

def dfs(depth):
    if depth == N:
        result.append(sum(abs(explore[i] - explore[i+1]) for i in range(N-1)))
        return
    for i in range(N):
        if visited[i]:
            continue
        explore.append(A[i])
        visited[i] = 1
        dfs(depth + 1)
        visited[i] = 0
        explore.pop()

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

visited = [0] * N
result, explore = [], []
dfs(0)
print(max(result))

---

📌 memo 😊

---

Ref)
https://velog.io/@kimdukbae/BOJ-10819-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%B5%9C%EB%8C%80%EB%A1%9C-Python