10819_차이를 최대로 (JAVA)

10819번: 차이를 최대로

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int ans = 0;
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		List<Integer> temp = new ArrayList<>();
		boolean[] checked = new boolean[N];
		int[] num = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st.nextToken());
		}

		func(num, temp, checked);

		System.out.println(ans);
	}

	private static void func(int[] num, List<Integer> temp, boolean[] checked){
		if(temp.size() == N){
			int cal = 0;
			for(int i=1; i<N; i++){
				cal += Math.abs(temp.get(i-1)-temp.get(i));
			}
			ans = Math.max(cal, ans);
		}

		for(int i=0; i<N; i++){
			if(!checked[i]){
				checked[i] = true;
				temp.add(num[i]);
				func(num, temp, checked);

				checked[i] = false;
				temp.remove(temp.size()-1);
			}
		}
	}
}

 

입력받는 N의 최대값은 8이다. 최악의 경우 8! 이므로, 모든 경우를 탐색해서 최대값을 출력하면 된다.

 

입력받은 N개의 숫자의 순서를 바꾸어야 한다. 

== N개의 숫자 중에서 N개를 뽑아 중복없이 순서있는 수열을 만드는 것과 같다.

== 순열 (nPn) 구하기

 

다만 체크해줘야될 것은, 우리는 최대값을 출력해야 하므로

nPn의 모든 경우를 탐색하고 그 과정에서 최대값을 변경해준다.

 

 

 

** 내가 생각한 방법!

나는 입력 범위를 체크하지 않아서, 모든 경우를 탐색하는 경우를 생각 못했다.

내가 생각한 방법은

오름차순 정렬 -> 왼쪽부터(최소값부터), 오른쪽부터(최대값부터) 를 왔다갔다하는.. 방법을 생각했다. (한 번에 정리가 안된다!)

 

예를 들어 설명하면,  (num[] = {20, 1, 15, 8, 4, 10}일 때)

 

1. 오름차순 정렬 : 1, 4, 8, 10, 15, 20

2. 최소값=1, 최대값=20 을 num[N/2-1], num[N/2-2] 자리에 넣는다. : - - 1 20 - - 가 된다.

3. - - 1 20 - - 에서,

   1을 기준으로 왼쪽으로, 20을 기준으로 오른쪽으로 이동하면서 숫자를 동시에 넣어준다.

   오름차순 정렬한 순서대로 숫자를 넣어주는데,

   1은 최소값이니까 20 다음 최대값인 15를 넣어주고,

   20은 최대값이므로 1 다음 최소값인 4를 넣어준다.

 

4. 순서대로 나열해보면 다음과 같다.

   - - 1 20 - -

   - 15 1 20 4 -

   8 15 1 20 4 10 : 이 경우가 출력값이 최대가 되는 경우가 된다!

 

 

근데 생각만 하고 구현을 못했다ㅎㅎㅎ 다음에 다시 풀어봐야지!