[JAVA][백준] 10819. 차이를 최대로

🔗링크

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

---

📑문제

---

🤔접근 방법

문제를 딱 봤을 땐 정렬을 해야한다고 생각해서 어떻게 정렬할지 오래 고민하다가
내가 정렬하면서 풀고 있는 방식이 브루트 포스 같아서(?) 모든 경우의 수를 구하는 방법으로 생각해봤다.

N의 범위도 8까지, 정수의 범위도 작아서 크게 문제 없었던 것 같다.

하나씩 뽑아서 res 배열에 저장해주고, 모든 값의 차이의 합을 더하는 doSum 함수를 만들어서 계산했다.

---

🗝️코드

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_10819_차이를최대로 {

	static int N;
	static int max = Integer.MIN_VALUE;
	static int[] arr, res;
	static boolean[] visited;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		arr = new int[N];
		res = new int[N];
		visited = new boolean[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		} // 배열의 값 입력받음

		dfs(0);
		System.out.println(max);

	}// main

	static void dfs(int depth) {

		// 기저
		if (depth == N) {
			// doSum으로 구한 현재의 결과와 max값 비교
			max = Math.max(doSum(), max);

			return;
		}

		// 재귀
		for (int i = 0; i < N; i++) {

			// 방문한 요소라면 넘어가기
			if (visited[i])
				continue;

			// 방문 안했다면
			if (!visited[i]) {

				// 방문처리 하고 값 넣어주고 한 단계 더 재귀
				visited[i] = true;
				res[depth] = arr[i];
				dfs(depth + 1);
				visited[i] = false;

			}

		}

	}// dfs

	static int doSum() {

		int sum = 0;

		// 인덱스 1로 시작하면서 내 앞에 있는 값과의 차이 sum에 저장하기
		for (int i = 1; i < N; i++)
			sum += Math.abs(res[i - 1] - res[i]);

		return sum;
	}// doSum

}