https://www.acmicpc.net/problem/10819
문제
> N개의 정수로 이루어진 배열 A가 주어진다.
> 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.
|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|접근
문제의 조건에 보면 N이 3이상 8이하가 된다.
범위가 매우 작다는 건 브루트포스를 이용할 수 있어진다.
가능한 모든 경우를 백트래킹으로 뽑아서 따져준다고하면 8! 즉, 약 4만번 x 계산 하는 연산(N-1)번까지 해서 충분하다. 따라서 재귀로 N개의 모든 수열을 따져 계산하고 최대값을 갱신해나간다.
문제해결
> N을 입력받고 num배열을 N크기로 선언해 초기 수열을 입력받는다.
> 순서를 바꿔 새로 만든 수열을 저장할 result 배열과 수를 중복사용하지 않기 위한 visited boolean형 배열도 선언한다.
> visited 배열을 false로 초기값 채워주고 수를 입력받은 뒤 백트래킹 메소드 A에 0을 넣어 호출한다.
> 인자로 뽑은 수열의 자릿수를 가지며 자릿수가 N개를 만족하면 문제의 계산식을 수행한다.
> 나온 결과를 최종결과값을 저장할 변수 Max에 갱신한다.
> rst가 N이 안되면 더 뽑아야하므로 재귀로 뽑는다.
> 매 재귀마다 0번 인덱스부터 뽑는데 중복 사용을 막기 위해 visited가 썼다고 마킹 되지 않은 수만 사용하도록 한다.
> 수를 뽑으면 마킹해주고 재귀로 넘긴다.
> 재귀가 깨져 돌아오면 다른 경우에서 해당 수를 또 쓸 수 있게 마킹을 복구해준다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//10819번 차이를 최대로
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N;
static int[] num, result;
static boolean[] visited;
static int Max = -1;
static public void A(int rst) {
if(rst == N) {
int sum = 0;
for(int i = 0; i < N - 1; i++) sum += Math.abs(result[i] - result[i+1]);
Max = Math.max(Max, sum);
return;
}
for(int i = 0; i < N; i++) {
if(visited[i]) continue;
result[rst] = num[i];
visited[i] = true;
A(rst + 1);
visited[i] = false;
}
}
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
num = new int[N];
result = new int[N];
visited = new boolean[N];
Arrays.fill(visited, false);
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
A(0);
System.out.print(Max);
}
}
후기
NtoM 문제의 응용 버전같았다. 처음엔 원리를 구해보려고 해서 고민했더니 수열을 오름차순 정렬했을 때 중앙에 있는 두 수를 각각 0, N-1인덱스에 배치해 한번만 계산되게 해주고 차례대로 젤 큰수, 젤 작은수 를 번갈아가며 배치하면 젤 커진다고 찾았다. 하지만 이 방식으론 최적의 해가 아니라고 한다. 애초에 N의 범위를 작게 줬으므로 이 문제는 백트래킹 브루트포스 문제라고 한다.
