[Baekjoon] 10819_차이를 최대로

Silver II

문제(출처: https://www.acmicpc.net/problem/10819)

---

< 차이를 최대로 >

 

문제 풀이 

 

정수를 놓을 수 있는 경우를 모두 다 해보기 위해 조합론을 사용한다.

 

 my solution (Java)

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

public class _10819_ { // 차이를 최대로
	static int arr[], result, arr2[];
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		st = new StringTokenizer(bf.readLine());

		arr = new int[n];
		arr2 = new int[n];
		visited = new boolean[n];
		result = 0;

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		search(0, n);
		System.out.println(result);
	}

	private static void search(int idx, int n) {
		if (idx == n) {
			int temp = 0;
			for (int i = 0; i < n - 1; i++) {
				temp += Math.abs(arr2[i] - arr2[i + 1]);
			}
			if (temp > result) {
				result = temp;
			}
			return;
		}

		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				arr2[idx] = arr[i];
				search(idx + 1, n);
				visited[i] = false;
			}
		}
	}
}

 

Main

변수)
arr : 배열 A 저장
result : 최댓값
arr2 : 순서를 바꾼 배열
visited : 방문 여부
n : 정수 수

 

- 정수 수(n) 입력

- 정수 입력받아 저장(arr)

- search 함수 호출

- 최댓값(result) 출력

 

search

- n개의 순서를 다 바꿨다면 차이를 계산해서 최댓값인지 확인 후 최댓값이면 값 업데이트

- 배열을 탐색하며 아직 방문하지 않은 곳이라면 방문 후 arr2에 저장 및 search 함수 호출. 호출 후에는 다시 방문 미표시

---

---