[백준 10819] 차이를 최대로 (C#, C++) - soo:bak

문제 링크

10819번 - 차이를 최대로

설명

배열의 순서를 바꿔 인접한 원소들의 절댓값 차이의 합이 최대가 되도록 만드는 문제입니다.

접근법

• 가능한 모든 순열을 만들어보며 차이의 합을 계산해야 하므로, 백트래킹(Backtracking)을 이용해 모든 경우를 탐색합니다.
• 각 단계에서 아직 사용하지 않은 수를 선택하여 순열을 구성하고 재귀적으로 다음 값을 탐색합니다.
• 이때 매 탐색마다 인접한 원소의 차이를 합산하여 최대값을 갱신합니다.

참고 : 백트래킹(Backtracking)의 개념과 구조적 사고 - soo:bak

---

Code

C#

using System;
using System.Linq;

class Program {
  static int max = 0, n;
  static int[] arr, permu;
  static bool[] used;

  static void Backtrack(int depth) {
    if (depth == n) {
      int sum = 0;
      for (int i = 1; i < n; i++)
        sum += Math.Abs(permu[i] - permu[i - 1]);
      max = Math.Max(max, sum);
      return;
    }

    for (int i = 0; i < n; i++) {
      if (!used[i]) {
        used[i] = true;
        permu[depth] = arr[i];
        Backtrack(depth + 1);
        used[i] = false;
      }
    }
  }

  static void Main() {
    n = int.Parse(Console.ReadLine());
    arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
    permu = new int[n];
    used = new bool[n];

    Backtrack(0);
    Console.WriteLine(max);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;

int n, mx;
vi a, p;
vb used;

void backtrack(int depth) {
  if (depth == n) {
    int s = 0;
    for (int i = 1; i < n; i++)
      s += abs(p[i] - p[i - 1]);
    mx = max(mx, s);
    return;
  }
  for (int i = 0; i < n; i++) {
    if (!used[i]) {
      used[i] = true;
      p.push_back(a[i]);
      backtrack(depth + 1);
      p.pop_back();
      used[i] = false;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  a.resize(n);
  used.resize(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  backtrack(0);
  cout << mx << "\n";

  return 0;
}