[백준] 10819번 차이를 최대로 (C++) - backtracking

문제

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

10819번: 차이를 최대로

코드

#include <iostream>

using namespace std;

int arr[8];
int arr2[8];
int isVisited[8];
int n;
int maxValue = -1;

void dfs(int cnt){
  if(cnt==n){
    int result = 0;
    for(int i=0; i<n-1; i++){
      result += abs(arr2[i+1]-arr2[i]);
    }
    if(result>maxValue) maxValue = result;
    return;
  }
  for(int i=0; i<n; i++){
    if(!isVisited[i]){
      isVisited[i] = true;
      arr2[cnt] = arr[i];
      dfs(cnt+1);
      isVisited[i] = false;
    }
  }
}

int main(){
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> arr[i];
  }
  dfs(0);
  cout << maxValue;
  return 0;
}

정리

https://kdongree.tistory.com/84 이 문제와 매우 유사한 문제이다. 전형적인 백트래킹 패턴 문제인 것 같다.

참조

https://kdongree.tistory.com/80

https://kdongree.tistory.com/84