백준 10819 C++

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

10819번: 차이를 최대로

 

+ C++의 next_permutation 함수를 사용하면 더 쉽게 풀 수 있다! 하지만 난 안 썼음

 

생각

1. 계산하고 비교하면서 큰 것만 남긴다!
근데 진짜 어떻게 해야할지 모르겠어
배열의 크기 제한이 8까지니까!! 작으니까 뭔가 하면 될 것 같아

 

코드 초안

int N, ans;
int arr[9];

int result(){ // 일케 계산하는 함수를 따로 만들고!
    int result = 0;
    for(int i = 0 ; i< N-1 ; i++){
        result += abs(arr[i] - arr[i+1]);
    }
    return result;
}

void dfs(int k){
    //dfs만 어케 잘 호출하면 될 것 같은데...
}

int main(){
    cin >> N;
    for(int i = 0 ; i<N ; i++){
        cin >> arr[i];
    }
    dfs(0);
    cout << ans; // 대충 이런 식으로...
}

 

정답 코드

#include <iostream>
using namespace std;

int N, ans;
int arr[9], temp[9];
bool visited[9];

int result(){
    int result = 0;
    for(int i = 0 ; i< N-1 ; i++){
        result += abs(temp[i] - temp[i+1]);
    }
    return result;
}

void dfs(int k){
    if(k == N){
        ans = max(ans, result());
    }
    for(int i = 0 ; i<N ; i++){
        if(!visited[i]){
            visited[i] = true;
            temp[k] = arr[i];
            dfs(k+1);
            visited[i] = false;
        }
    }
}

int main(){
    cin >> N;
    for(int i = 0 ; i<N ; i++){
        cin >> arr[i];
    }
    for(int i = 0 ; i<N ; i++){
        visited[i] = true;
        temp[0] = arr[i];
        dfs(1);
        visited[i] = false;
    }
    cout << ans;
}

 

이 코드에서 포인트는 visited를 main에서 / dfs에서 쓰는 것이다!

같은 visited 함수가 아님!! 서로 다르게 쓰이는데 그냥 재활용함 하하

 

 - main 함수에서 visited 배열을 사용하는 목적

 각 요소를 순열의 시작 요소로 선택하는 초기 상태를 설정하는 것!

   = 첫 번째 숫자를 결정하고 조합을 계속 바꾼다는 뜻입니다~~~

 - dfs 함수에서 visited 배열을 사용하는 목적

 dfs 함수는 재귀적으로 호출되면서 각 순열을 구성하는 과정에서 visited 배열을 사용함!

   = 님들이 아는 그냥 방문 체크 후 dfs 돌리는 그거입니다~~~