백준(BOJ) 10819 : 차이를 최대로 (실버2) / 자바(Java) 풀이

문제

https://www.acmicpc.net/problem/10819

3줄 요약

1. 정수의 개수 N과 N개의 정수로 이루어진 배열 A를 입력받습니다.
2. 백트래킹을 활용하여 재귀 함수를 사용해 순열을 생성하고, 생성된 순열에 대해 인접한 요소의 차이의 절댓값의 합을 계산합니다.
   • 백트래킹은 모든 경우의 수를 탐색하되, 조건에 맞지 않는 경우는 더 이상 탐색하지 않고 가지치기하는 기법입니다.
   • 이 문제에서는 순열을 생성하는 과정에서 백트래킹을 적용합니다. 재귀 함수에서 현재 선택한 요소를 배열 B에 저장하고, 다음 요소를 선택할 때는 이전에 선택한 요소를 제외하고 선택합니다.
   • 만약 현재 선택한 요소로 인해 순열을 완성할 수 없는 경우, 해당 요소를 선택하지 않고 백트래킹하여 다른 요소를 선택합니다. 이를 통해 불필요한 탐색을 줄일 수 있습니다.
   • 순열이 완성되었을 때, 인접한 요소의 차이의 절댓값의 합을 계산하고 최댓값을 갱신합니다.
3. 인접한 요소의 차이의 절댓값의 합 중 최댓값을 출력합니다. 이 문제에서는 백트래킹을 활용한 재귀 함수를 통해 순열을 효율적으로 생성하고, 생성된 순열에 대해 문제에서 요구하는 계산을 수행함으로써 문제를 해결할 수 있습니다. 백트래킹을 사용하여 불필요한 탐색을 줄임으로써 효율적인 알고리즘을 구현할 수 있습니다.

코드

// package boj10819;

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력 파일에서 데이터 읽기 (테스트용)
        // System.setIn(new FileInputStream("src/input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 정수의 개수 N 입력받기
        int N = Integer.parseInt(br.readLine());
        
        // 정수 배열 A 입력받기
        String[] arr = br.readLine().split(" ");
        A = new int[N];
        B = new int[N];
        for (int i = 0; i < A.length; i++) {
            A[i] = Integer.parseInt(arr[i]);
        }
        
        br.close();
        
        // 순열 생성 및 최댓값 계산
        recursion(N, 0);
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(max));
        bw.flush();
        bw.close();
    }
    
    public static int[] A; // 입력받은 정수 배열
    public static int[] B; // 생성된 순열을 저장할 배열
    public static boolean[] visited = new boolean[9]; // 방문 여부를 체크할 배열
    public static int max = 0; // 최댓값을 저장할 변수
    
    public static void recursion(int N, int depth) {
        // 순열이 완성되었을 때
        if (N == depth) {
            int sum = 0;
            // 인접한 요소의 차이의 절댓값의 합 계산
            for (int i = 0; i < B.length - 1; i++) {
                sum += Math.abs(B[i] - B[i+1]);
            }
            // 최댓값 갱신
            max = Math.max(max, sum);
            return;
        }
        
        // 순열 생성
        for (int i = 0; i < N; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            B[depth] = A[i];
            recursion(N, depth + 1);
            visited[i] = false;
        }
    }
}