BOJ 10819 - 차이를 최대로

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

10819번: 차이를 최대로

아이디어

N개의 정수를 중복을 허용하지 않고 순서있게 나열하는 순열문제이다.

먼저 가능한 순열을 완전탐색을 통해 다 뽑고 난 후 주어신 식에 대입해서 최댓값을 갱신한다.

시간복잡도

N의 최댓값은 8 이므로 순열의 시간복잡도인 O(N!)에 대입하면 8! < 1초라서 가능한 접근법이다.

구현

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int[] nums, selected, visit;
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        init();

        rec_func(1);

        bw.write(max+" ");

        bw.close();
    }

    static void rec_func(int k) throws IOException {
        if (k == N + 1) {

            // 조건 식 계산
            calculate();

        } else {
            for (int i = 1; i <= N; i++) {
                int n = nums[i];

                if(visit[i] ==1) continue;

                selected[k] = n;
                visit[i] = 1;

                rec_func(k+1);

                selected[k] = 0;
                visit[i] = 0;
            }
        }
    }

    static void calculate() throws IOException {
        int sum = 0;
        for (int i = 1; i <= N-1; i++) {
            sum += Math.abs(selected[i] - selected[i+1]);
        }

//        bw.write(sum+"\n");

        max = Math.max(max, sum);

    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        selected = new int[N + 1];
        nums = new int[N + 1];
        visit = new int[N + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

    }
}