백준 10819번: 차이를 최대로 with Java

차이를 최대로

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

35258

23134

17906

66.294%

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1 복사

6
20 1 15 8 4 10

예제 출력 1 복사

62

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

 

 

---

 

이거 걍 바꿔가면서 풀어버리면 되는 거 아니여? 키키

3에서 8까지니까!!!!

 

DFS도 쓸 수 있을 것 같긴 한데.. 완탐으로 풀어보려고 했다.

일단 다 확인해보려면 정렬하고 사전순으로 다 생성해서 확인하면 되겟쥬

 

아...

이거 은근 스왑하는 부분 짜기가.. .기억이 안 나서 힘들었다

이럴거면 dfs가 쉬웠을지도;;;

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    // 배열 순서 바꾸기
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 다음 순열 생성 (사전순으로)
    private static boolean nextPermutation(int[] arr) {
        int i = arr.length - 1;
        
        // 뒤에서부터 내림차순이 끝나는 지점을 찾음
        while (i > 0 && arr[i - 1] >= arr[i]) i--;

        // i가 0이면 전부 내림차순이니까 false return
        if (i == 0) return false;

        int j = arr.length - 1;
        while (arr[i - 1] >= arr[j]) j--;

        swap(arr, i - 1, j);

        // i부터 끝까지 뒤집기
        int k = arr.length - 1;
        while (i < k) {
            swap(arr, i, k);
            i++;
            k--;
        }

        return true;
    }

    // 인접한 수들의 차이 합 계산
    private static int calculate(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            sum += Math.abs(arr[i] - arr[i + 1]);
        }
        return sum;
    }

    // 메인 함수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // 가장 작은 순열로 시작
        Arrays.sort(A);

        int max = Integer.MIN_VALUE;

        // 모든 순열에 대해 최대값 탐색
        do {
            int result = calculate(A);
            max = Math.max(max, result);
        } while (nextPermutation(A));

        System.out.println(max);
    }
}

 

순열 오름차순해서 하나씩 바꿔가면서 더하는 완전 탐색이엇습니다요...