[백준] 10819번 : 차이를 최대로

문제

10819번: 차이를 최대로

 

접근 방식

쉬운 조합 문제인데 문제를 잘못 봐서 헤맸다.

 

abs(num[0] - num[1]) + abs(num[2] - num[3]) + ... +  abs(num[n - 2] - num[n -1]) 가 아니라

abs(num[0] - num[1]) + abs(num[1] - num[2]) + ... +  abs(num[n - 2] - num[n -1]) 인 부분을 조심해야 한다.

 

이 부분만 조심하면서 재귀 호출 시 파라미터로 이전까지의 계산을 넘겨주면서

백트래킹을 이용해 조합만 해주면 된다.

 

이전에 고른 수를 알고 있어야 하기 때문에

추가로 배열을 사용해 수를 기록해두면 편리하다.

 

풀이

public class Main {

	static int n, max = -1000000;
	static int[] arr, nums;
	static boolean[] isUsed;

	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];
		nums = new int[n];
		isUsed = new boolean[n];

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

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

		solve(0, 0);

		System.out.println(max);
	}

	static void solve(int cnt, int sum) {
		if (cnt == n) {
			max = Math.max(max, sum);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (isUsed[i]) continue;
			isUsed[i] = true;
			nums[cnt] = arr[i];
			if (cnt == 0) solve(cnt + 1, sum);
			else solve(cnt + 1, sum + Math.abs(nums[cnt - 1] - nums[cnt]));
			isUsed[i] = false;
		}
	}
}