알고리즘 풀이 - 백준 10819(차이를 최대로, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

순열 중에서 인접 수 끼리의 차이의 합이 가장 큰 결과값을 구하는 문제

 

 

2. 풀이

 

이전 / 다음 순열 문제의 로직을 그대로 사용해서 풀 수 있는 문제이다.

현재 주어진 숫자의 배열에서 최초 순열까지 이전 순열을 구하면서 인접 수 차이 합 중 최대를 구하고, 최종 순열까지 다음 순열을 구하며 동일한 작업을 수행하면 된다.

 

또는, 정렬을 수행한 뒤, 다음 순열을 구해가며 인접 수 간 차이 합 중 최대를 구한다. 아래의 코드에서는 이 방법을 사용하였다.

다음 순열을 구하는 방법은 아래 내용을 참고한다.(자세한 순열 관련 내용은 상단의 완전 탐색 포스팅 링크를 통해 참고)

※ 순열을 구현하는 방법

현재 순열을 구성하는 배열을 A라고 하고 i,j는 그 배열의 index 값을 의미한다고 하자. 예를 들어 A={7, 2, 3, 6, 5, 4, 1}이고 i, j는 각각의 index 값이다.

아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.


1. A[i-1] <= A[i]를 만족하는 i 중 가장 큰 값을 찾는다.(혹은 뒤에서부터 찾는 경우 A[i-1] >= A[i] 중 가장 작은 i를 찾는다.)
  → 현재 i값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는 다는 것이다. 현재 기준 최종 순열을 찾음
      A배열을 보면 A[i-1] < A[i]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.

2. j >=>= i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.
  → 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾아야 한다.
      A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.

3. A[i-1]과 A[j]를 Swap한다.
   → i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 6, 5, 3, 1}

4. i이후의 순열을 모두 뒤집는다.
   → 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 1, 3, 5, 6}

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int perm[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        perm = new int[n];
        
        for(int i=0; i < n; i++){
            perm[i] = Integer.parseInt(line[i]);
        }
        
        // 정렬을 통해 최초 순열 상태로 만든다.
        Arrays.sort(perm);
        
        // 최초 순열일 때의 인접 수 간 차이 합을 구한다.
        int max = calc();
        
        while(true){
            boolean isNext = getNext();
            
            // 최종 순열까지 왔다면 반복문 탈출
            if(!isNext) break;
            
            max = Math.max(max, calc());
        }
        
        bw.write(String.valueOf(max));
        bw.flush();
        br.close();
    }
    
    // 다음 순열을 찾는 메소드
    private static boolean getNext(){
        int i = n-1;
        while(i > 0 && perm[i-1] >= perm[i]) i--;
        
        if(i <= 0) return false;
        
        int j = i-1;
        while(j < n-1 && perm[j+1] > perm[i-1]) j++;
        swap(i-1, j);
        
        j = n-1;
        while(i < j){
            swap(i, j);
            i+=1; j-=1;
        }
        return true;
    }
    
    // swap을 수행
    private static void swap(int i, int j){
        int temp = perm[i];
        perm[i] = perm[j];
        perm[j] = temp;
    }
    
    // 인접 수 사이의 값의 차이를 다 더하는 메소드
    private static int calc(){
        int result = 0;
        for(int i=0; i < n-1; i++){
            result += Math.abs(perm[i+1] - perm[i]);
        }
        return result;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.