[백준] 10819 : 차이를 최대로

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

10819번: 차이를 최대로

---

• 숫자가 최대 8개 밖에 되지 않기 떄문에, 완전탐색으로 전부 검사 가능하다.
• 백트래킹을 통해 하나의 재귀호출마다 자릿수 하나를 채워넣는다.
• 첫 자리의 값을 N 개 중 하나로 결정하면, 두번째 자리로 들어가 나머지 N-1 개 중 하나를 뽑고, 세번째 자리에서는 N-2 개 중 하나를 뽑는 식으로 재귀가 들어간다.
• permutation 관련 함수들을 사용해도 괜찮을 것 같다.

---

#include <iostream>

using namespace std;

int N;
int values[8];      // 입력 값들
int answer[8];      // N 개 순서를 바꿔가며 뽑아줄 배열
bool visit[8];      // 뽑을 때 중복되지 않게 관리해주는 배열
int maxi = 0;

void select_next(int depth)
{
    if(depth == N)                          // N 개를 다 뽑았다면
    {
        int temp = 0;
        for(int i = 0 ; i < N-1 ; i++)      // 수식에 맞는 값 구하고
        {
            temp += abs(answer[i] - answer[i+1]);
        }
        if(temp > maxi) maxi = temp;        // 최댓값 갱신
        return;
    }

    for(int i = 0 ; i < N ; i++)            // 이번 자릿수의 값 선택
    {
        if(visit[i]) continue;              // 앞에서 뽑힌 값이라면 넘어감
        visit[i] = true;
        answer[depth] = values[i];          // 이번 자릿수에서 값 넣어주고
        select_next(depth + 1);             // 다음 자릿수의 값 선택
        visit[i] = false;
    }
}

int main(void)
{
    cin >> N;
    for(int i = 0 ; i < N ; i++) cin >> values[i];
    select_next(0);
    cout << maxi << endl;
}