[ 백준 10819번 ] 차이를 최대로

1. 문제

10819번: 차이를 최대로

 

2. 풀이

뭔가 주어진 수열의 연속된 부분합의 최대를 구하는 것이 수학적인 공식으로 해결할 수 있을 것 같기도 한데... 귀찮아서 백트래킹으로 풀었읍니다...

 

백트래킹을 시도할 수 있는 근거는, 문제에서 주어진 정수 배열의 범위가 최대 8로 8!의 경우의 수만 해결해주면 되기 때문이다. 따라서 배열에서 중복되지 않는 순열을 만드는 기법을 이용해 합을 산정해주었다. 이 때 매개변수로 이전 idx를 넘겨줌으로써 연속된 idx들의 합을 계속해서 더해나갈 수 있도록 처리하였다.

 

3. 소스코드

public class Main {
    static int N;
    static int[] arr;
    static boolean[] visit;
    static int ans = -801;

    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());

        arr = new int[N];
        visit = new boolean[N];

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

        backtracking(0, 0, -1);

        bw.write(ans + "");
        bw.close();
        br.close();
    }

    static void backtracking(int sum, int cnt, int preIdx) {
        if (cnt == N) {
            ans = Math.max(ans, sum);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            if (preIdx != -1) {
                backtracking(sum + Math.abs(arr[i] - arr[preIdx]), cnt + 1, i);
            } else {
                backtracking(sum, cnt + 1, i);
            }
            visit[i] = false;
        }
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code