백준 10819번 차이를 최대로(java)

[Silver II] 차이를 최대로 - 10819

문제 링크

성능 요약

메모리: 15248 KB, 시간: 180 ms

분류

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

제출 일자

2024년 7월 23일 23:56:19

문제 설명

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

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

입력

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

출력

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

 

풀이

새로운 배열을 만들어서 dfs를 호출할 때 마다 배열을 쌓아가는 방식과 단순하게 모든 요소를 전부 swap하는 방식 두 가지를 떠올렸다. 더 효율적인 방식은 새롭게 배열을 만드는 방식이라고 생각이 들었으나 우선 간단하게 구현할 수 있는 모든 요소를 바꾸는 방식으로 코드를 구현해 봤다.

 

public static void swap(int x[], int k){
    int flag = 0;
    flag = x[k];
    x[k] = x[k+1];
    x[k+1] = flag;
}

 

다음과 같이 swap을 하고 dfs를 호출하며 모든 요소의 위치가 바뀌도록 했다.

 

public static void dfs(int k){
    if(sum(original) > max){
        max = sum(original);
    }
    for(int j = k;j<N-1;j++) {
        for (int i = 0; i < N - 1; i++) {
            swap(original, i);
            dfs(j + 1);
        }
    }

}

 

다만 이 방식은 중복되는 순열이 많이 나오기에 조금 비효율적인 방식이다. 

맨 처음 생각한 빈 배열에 하나씩 쌓아가며 순열을 만드는 방식에 true false를 추가하면 좀 더 효율적으로 만들 수 있을 것 같다. 해당 방식으로도 코드를 한 번 구현해 봐야겠다.

 

public class Main{
    static int N,max=0,original[];
    static Boolean selec[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String num = br.readLine();
        N = Integer.parseInt(num);

        int a;

        original = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int  i = 0 ;i<N;i++){
            original[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0);

        bw.write(String.valueOf(max));
        bw.flush();

    }

    public static void dfs(int k){
        if(sum(original) > max){
            max = sum(original);
        }
        for(int j = k;j<N-1;j++) {
            for (int i = 0; i < N - 1; i++) {
                swap(original, i);
                dfs(j + 1);
            }
        }

    }

    public static int sum(int x[]){
        int s = 0;

        for(int i = 0 ;i<N-1;i++){
            s += Math.abs(x[i] - x[i+1]);
        }

        return s;
    }

    public static void swap(int x[], int k){
        int flag = 0;
        flag = x[k];
        x[k] = x[k+1];
        x[k+1] = flag;
    }


}