코딩테스트
백준 10819번: 차이를 최대로[JAVA]
stdio.han
2024. 3. 21. 20:28
https://www.acmicpc.net/problem/10819
10819번: 차이를 최대로
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
www.acmicpc.net
[정답 코드]
import java.io.*;
import java.util.*;
public class Main {
static int result = Integer.MIN_VALUE;
static int N;
static int[] arr, selected;
static boolean[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
arr = new int[N];
visited = new boolean[N];
selected = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
dfs(0);
System.out.println(result);
}
public static void dfs(int count) {
if (count == N) {
result = Math.max(result, getResult());
return;
}
for (int i = 0; i < N; i++) { //
if (!visited[i]) {
visited[i] = true;
selected[count] = arr[i];
dfs(count + 1);
visited[i] = false;
}
}
}
public static int getResult() {
int sum = 0;
for (int i = 0; i < N - 1; i++) {
sum += Math.abs(selected[i] - selected[i + 1]);
}
return sum;
}
}
[설명]
부르트 포스 알고리즘과 dfs를 활용해 풀었다. for문을 돌며 깊이 우선 탐색으로 count가 N이 될 때 까지 탐색하다 count 가 N이 될 경우 getResult() 메서드를 실행해 지금까지 저장했던 result 값과 비교해 최댓값을 출력한다. getResult() 메서드는 dfs 알고리즘을 돌며 count가 N이 될 때 까지 선택해왔던 숫자들을 담은 배열을 계산해주는 메서드이다.