No Rules Rules

차이를 최대로 (feat. 백준, 10819번) 본문

생활/코테

차이를 최대로 (feat. 백준, 10819번)

개발하는 완두콩 2022. 11. 1. 13:21
728x90
반응형

차이를 최대로
https://www.acmicpc.net/problem/10819

 

10819번: 차이를 최대로

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

www.acmicpc.net

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int N, arr[8], tmp[8], ans;
bool visit[8];
void dfs(register int cnt){
    if(cnt == N){
        register int sum = 0;
        for(register int i = 0; i < N - 1; ++i)
            sum += abs(tmp[i] - tmp[i + 1]);
        ans = max(ans, sum);
        return;
    }
    for(register int i = 0; i < N; ++i)
        if(!visit[i]){
            visit[i] = true;
            tmp[cnt] = arr[i];
            dfs(cnt + 1);
            visit[i] = false;
            tmp[cnt] = 0;
        }
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    ans = -100;
    cin >> N;
    for(register int n = 0; n < N; ++n)
        cin >> arr[n], visit[n] = false;
    dfs(0);
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

dfs를 이용한 순열을 통해 문제의 조건으로 계산된 최대값을 찾습니다.

728x90
반응형
Comments