문제 푼 날짜 : 2021-09-18

문제

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

접근 및 풀이

간단한 백트래킹 문제였다.
순열을 구현하여 간단히 해결해줄 수 있었다.
next_permutation을 이용해서도 구현해 보았다.

코드(백트래킹)

// 백준 10819번 : 차이를 최대로
#include <iostream>
#include <algorithm>

using namespace std;

int N, ans = -987654321;
int arr[9], ret[9];
bool visited[9] = { false, };

void dfs(int cnt) {
    if (cnt == N) {
        int sum = 0;
        for (int i = 0; i < N - 1; i++) {
            sum += abs(ret[i] - ret[i + 1]);
        }
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i < N; i++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        ret[cnt] = arr[i];
        dfs(cnt + 1);
        visited[i] = false;
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    dfs(0);

    cout << ans;
    return 0;
}

코드(완전탐색)

// 백준 10819번 : 차이를 최대로
#include <iostream>
#include <algorithm>

using namespace std;

int N;
int arr[9];

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    int diff = -987654321;
    sort(arr, arr + N);

    do {
        int sum = 0;
        for (int i = 0; i < N - 1; i++) {
            sum += abs(arr[i] - arr[i + 1]);
        }
        diff = max(diff, sum);
    } while(next_permutation(arr, arr + N));

    cout << diff;
    return 0;
}

결과

피드백

더 익숙해질 때까지