백준 10819번 차이를 최대로 - C++(cpp) 풀이

---

 

1. N개의 정수의 순서를 정하는 경우의 수는 N!
2. N이 작으므로 모든 경우를 탐색하여 주어진 식이 최대가 되는 경우를 찾는다.

 

1. N개의 정수의 순서를 정하는 경우의 수는 N!

 크기가 N인 배열에 들어있는 수들의 순서를 바꾸는 경우의 수는 N!이다.

 

2. N이 작으므로 모든 경우를 탐색하여 주어진 식이 최대가 되는 경우를 찾는다.

 N이 최대 8이므로 8! = 40,320가지밖에 되지 않는다. 따라서 시간 내에 모두 탐색하는 것이 가능하다. 재귀와 비트 마스크를 이용해서 모든 경우를 탐색하고 최대가 되는 경우를 찾으면 된다.

 

반응형

---

#include <iostream>
#include <cmath>
#include <string.h>

using namespace std;

int N;
int arr[8], pick[8];

int brute_force(int idx, int mask) {
    if (idx == N) {
        int ret = 0;
        for (int i=0; i<N-1; i++) {
            ret += abs(arr[pick[i+1]] - arr[pick[i]]);
        }
        return ret;
    }
    
    int ret = 0;
    
    for (int i=0; i<N; i++) {
        if ((mask & (1 << i)) != 0) continue;
        pick[idx] = i;
        ret = max(ret, brute_force(idx+1, mask|(1<<i)));
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) cin >> arr[i];
    
    cout << brute_force(0, 0);

    return 0;
}