[백준] 10819번 : 차이를 최대로
문제 푼 날짜 : 2021-09-18
문제
문제 링크 : https://www.acmicpc.net/problem/10819
접근 및 풀이
간단한 백트래킹 문제였다.
순열을 구현하여 간단히 해결해줄 수 있었다.
next_permutation을 이용해서도 구현해 보았다.
코드(백트래킹)
// 백준 10819번 : 차이를 최대로
#include <iostream>
#include <algorithm>
using namespace std;
int N, ans = -987654321;
int arr[9], ret[9];
bool visited[9] = { false, };
void dfs(int cnt) {
if (cnt == N) {
int sum = 0;
for (int i = 0; i < N - 1; i++) {
sum += abs(ret[i] - ret[i + 1]);
}
ans = max(ans, sum);
return;
}
for (int i = 0; i < N; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
ret[cnt] = arr[i];
dfs(cnt + 1);
visited[i] = false;
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
dfs(0);
cout << ans;
return 0;
}
코드(완전탐색)
// 백준 10819번 : 차이를 최대로
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int arr[9];
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int diff = -987654321;
sort(arr, arr + N);
do {
int sum = 0;
for (int i = 0; i < N - 1; i++) {
sum += abs(arr[i] - arr[i + 1]);
}
diff = max(diff, sum);
} while(next_permutation(arr, arr + N));
cout << diff;
return 0;
}
결과
// 백준 10819번 : 차이를 최대로
#include <iostream>
#include <algorithm>
using namespace std;
int N, ans = -987654321;
int arr[9], ret[9];
bool visited[9] = { false, };
void dfs(int cnt) {
if (cnt == N) {
int sum = 0;
for (int i = 0; i < N - 1; i++) {
sum += abs(ret[i] - ret[i + 1]);
}
ans = max(ans, sum);
return;
}
for (int i = 0; i < N; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
ret[cnt] = arr[i];
dfs(cnt + 1);
visited[i] = false;
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
dfs(0);
cout << ans;
return 0;
}
// 백준 10819번 : 차이를 최대로
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int arr[9];
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int diff = -987654321;
sort(arr, arr + N);
do {
int sum = 0;
for (int i = 0; i < N - 1; i++) {
sum += abs(arr[i] - arr[i + 1]);
}
diff = max(diff, sum);
} while(next_permutation(arr, arr + N));
cout << diff;
return 0;
}
결과
피드백
더 익숙해질 때까지
Author And Source
이 문제에 관하여([백준] 10819번 : 차이를 최대로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bestcoders/백준-10819번-차이를-최대로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)