Before we start off..

오늘은 자바 내용 정리가 아닌 백준 문제 포스팅을 해보겠습니다. 알고리즘을 시작하면서 아마 이론 정리도 올리겠지만, 주로 문제 풀이를 더 올릴 것 같습니다.

Problem

문제 링크: https://www.acmicpc.net/problem/10819

어떤 N개의 원소를 갖는 배열이 있습니다. 그 배열을 적절히 섞어서 다음 식이 최대가 되게 만들면 됩니다.

문제를 이해하는데 오래 걸리진 않습니다. 그리고 방법을 생각해내기 까지도 얼마 안걸립니다.

Approach

처음에 생각나는건 Brute force입니다. Permutation을 활용해서 가능한 모든 수열을 만들고, 차이값이 최대가 되는 값을 찾으면 됩니다. 하지만, 엄청난 시간복잡도 앞에서 방향을 틀게 됩니다.
두번째로 생각나는것은 백트래킹입니다. depth와 recursion의 개념을 사용해 수열을 좀더 유연하게 만들었다 지울 수 있습니다.

Solution

public static void diffToMax(int depth) {
		if(depth == len) {
			int sum = 0;
			for(int i = 0; i < len - 1 ; i++) {
				sum += Math.abs(bag[i] - bag[i+1]);
			}
			//System.out.println(sum);
			optimum = Math.max(optimum, sum);
			return;
		}
		
		for(int i = 0; i < len ; i ++) {
			if(visited[i]) continue;
			visited[i] = true;
			bag[depth] = target[i];
			diffToMax(depth + 1);
			visited[i] = false;
		}
	}

diffToMax는 재귀를 전제로 실행되는 메서드입니다. 따라서 종료조건을 먼저 세웠습니다. 우리가 원하는 길이의 수열이 생겼을때, 차이값을 계산하고, 최댓값을 갱신합니다.

그런 경우가 아니면, visited를 이용해 bag에서 depth에 맞는 자리에 수를 바꿔넣으면서 함수를 재호출해줍니다.

import java.util.Scanner;
public class Main{
	static int[] target;
	static int[] bag;
	static boolean[] visited;
	static int len;
	static int optimum;
	
	public static void diffToMax(int depth) {
		if(depth == len) {
			int sum = 0;
			for(int i = 0; i < len - 1 ; i++) {
				sum += Math.abs(bag[i] - bag[i+1]);
			}
			//System.out.println(sum);
			optimum = Math.max(optimum, sum);
			return;
		}
		
		for(int i = 0; i < len ; i ++) {
			if(visited[i]) continue;
			visited[i] = true;
			bag[depth] = target[i];
			diffToMax(depth + 1);
			visited[i] = false;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		len = sc.nextInt();
		target = new int[len];
		bag = new int[len];
		visited = new boolean[len];
		
		for(int i = 0 ; i < len ; i++) {
			target[i] = sc.nextInt();
		}

		diffToMax(0);
		System.out.println(optimum);
	}
}

전체 코드입니다. Main에서는 단순하게 입력값을 처리해주고, diffToMax함수를 호출합니다.

Conclusion

오늘 배운 백트래킹에 대해 잘 복습할 수 있던 문제였습니다!