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

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, max_n;
int arr[8], perm[8];
bool visited[8];

void dfs(int idx)
{
    if(idx==n) //최대값 계산
    {
        int sum = 0;
        for(int i=0; i<n-1; i++)
        {
            int gap = abs(perm[i]-perm[i+1]); 
            sum+=gap;
        }
        max_n = max(max_n, sum);
        return;
    }

    for(int i=0; i<n; i++)
    {
        if(visited[i]) continue;
        visited[i] = 1; //현재 숫자 선택
        perm[idx] = arr[i]; //순열에 값 저장
        dfs(idx+1);
        visited[i] = false; //백트래킹 (선택 취소)
    }

}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];

    dfs(0);

    cout << max_n;

    return 0;
}

 

백트래킹을 이용해 푸는 문제이다.

먼저 처음 위치인 0부터 시작하여 최대 idx가 n에 도달할 때 해당 조합에 대한 차이 값을 계산하며 최대값도 비교해준다.

 

조합하는 과정은 방문 배열을 통해 현재 숫자가 선택되었는지, 취소되었는지를 체크해주고,

순열 배열에 현재 배열 값을 담아준다.

이후에 인덱스를 증가시켜 다음 값을 체크하게 되며 이 인덱스가 n에 도달 하면 위에서 설명했단 계산을 거치게 된다.

선택했던 값을 재귀를 돌고 이후에 취소 시켜주어야만 다른 조합에서 쓸 수 있음에 주의해야한다.