백준 10819번: 차이를 최대로 C++ 코드(브루트포스, Bruteforce)

#include<iostream>
#include<vector>

using namespace std;

int n;
int a[10];
int maxi = 0; //최대값

void func(vector <int> v, int visited[10]){
    if(v.size() == n){
        int result = 0;
        
        for(int i = 0; i<n-1; i++){
            result += abs(v[i] - v[i+1]);
        }
        if(result > maxi){
            maxi = result;
        }
    }
    for(int i=0; i<n; i++){
        if(visited[i] == 0){
            v.push_back(a[i]);
            visited[i] = 1;
            func(v, visited);
            v.pop_back();
            visited[i] = 0;
        }
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    vector <int> v;
    int visited[10] = {0,};
    
    func(v, visited);
    cout << maxi;

}

 

설명

오랜만에 문제를 푸니 조금 헤매는 감이 있었다. 

입력을 받고, 순서를 정해서 넣을 벡터와 넣은 수를 표시하기 위한 visited를 만들어준다.

 

반복문을 돌려서 i번째 원소를 벡터에 넣고 visited[i]를 1로 바꾼다.

그리고 이 상태로 벡터와 visited를 다시 함수에 매개변수로 넣어서 함수를 실행한다.

그리고 다시 벡터에 넣은 원소를 빼고, visited[i]를 0으로 바꾼다.

 

이것을 반복하다가 벡터의 크기가 n이 되면 abs(v[0]-v[1]) + abs(v[1]-v[2]) +....abs(v[n-2]-v[n-1])를 구한 뒤에 전역변수로 선언해둔 maxi(max는 예약어라서 maxi로..)와 비교를 해서 maxi보다 크면 maxi를 위에서 구한 값으로 바꿔준다.

 

이 과정을 계속 반복하다 모든 함수가 종료되었을 때 maxi를 출력하면 된다.

 

문제점

백트래킹을 사용하려면 미리 차이값이 작은지 큰지를 비교해야하는데 이 연산을 만들기 애매해서 브루트포스로 코드를 짰다.