백준 10819 차이를 최대로

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

10819번: 차이를 최대로

모든 순열을 구해서 문제의 규칙대로 더했을때 최대가 되는 값을 뽑아내면 되는 간단한 문제 입니다.

모든 순열을 구하는 방법은 아래와 같이 하셔도 되고 다른 방법이 있다면 그방법을 이용하시면됩니다.

왜 순열은 구할때 다중 포문을 이용하지 않았는지 간단히 말쓰드리면 

예전에 이런 방식을 할때 다중포문으로 구현을 하려했습니다. 위 문제와 같이 N이 8이면 적어도 8중포문이상 사용을 

해야 가능한데 N이 들어올때마다 다중포문을 8이면 8개 6이면 6개 해야하기때문에 상당히 까다롭습니다.

물론 구현이 불가능 하다는것은 아닙니다. 

재귀를 이용하여 백트래킹을 하면 쉽다는 것입니다. 재귀 백트래킹은 다만 깊이가 깊어지면 시간이 오래걸리는 단점이

있지만 위와 같이 N이 적으면 가장 간단한 방법이니 틀을 이해가 어렵다면 외워서 이해를 하시면됩니다.

아래와같이 구현을 하면

이렇게 순열이 뽑아지는데 

이렇게 뽑으면서 계산을 해서 최대값을 갱신해주면서 최대값은 이거다 해주면 되는 간단한 문제 

내가 재귀를 이용해 모든순열을 알고 있다면 그냥 풀리는 문제이니 이런유형은 바로 풀어봅시다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int N;
int input[9];
int num[9];
int chk[9];
int ret = 0x80000000;
void dfs(int idx) {
    if (idx == N) {
        int sum = 0;
        for (int y= 0; y < N - 1; y++) {
            sum += abs(input[num[y]] - input[num[y+1]]);
        }
        ret = max(ret, sum);
        return;
    }
    else {
        for (int i = 0; i < N; i++) {
            if (num[idx] == -1 && chk[i] == 0) {
                num[idx] = i;
                chk[i] = 1;
                dfs(idx + 1);
                chk[i] = 0;
                num[idx] = -1;
            }
        }
    }
}
void init() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        num[i] = -1;
        scanf("%d", &input[i]);
    }
}
int main(void) {
    init();
    dfs(0);
    printf("%d\n", ret);
    return 0;
}