Baekjoon (백준) 10819 번

💻 Beakjoon 10819 번 문제 -Java

• Baekjoon 10819 번

문제 설명

문제의 설명은 간단하다.

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

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

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

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

접근 방법

Backtracking 알고리즘으로 접근해서 코드를 구현 하였다.

문제 풀이

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

public class Baek_j_10819 {
    static int N;
    static int input[];
    static int max = Integer.MIN_VALUE;
    static boolean vi[];
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        input = new int[N];
        vi = new boolean[N];

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

        dt(0,0,0);

        System.out.println(max);

    }
    // dep : 깊이. prev : 이전 값을 넣는 변수, sum : 총 합계
    public static void dt(int dep, int prev, int sum){

        if(dep == N){
            max = Math.max(max,sum);
            return;
        }
        for(int i = 0; i < N; i++){
            if(!vi[i]){
                vi[i] = true;
                // 깊이 증가, 현재값, 깊이가 0일 때는 합계가 없으므로 0, 1이상일때는 이전 값과 현재 값을 빼서 합계랑 더함.
                dt(dep+1, input[i], dep == 0 ? 0: sum + Math.abs(input[i]-prev));
                vi[i] = false;

            }
        }

    }
}

💡 문제 해결 과정 느낌점

• 그렇게 어려운 문제는 아니였다. 문제를 잘 이해하고 문제에서 설명한데로 직관적으로 코드를 구현하니 정답이였다.