백준 10819 차이를 최대로 Kotlin (순열)

문제 출처 : https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

문제

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

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

입력

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

출력

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

알고리즘 분류

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

풀이

간단한 순열 문제이다.

조합이 아니라 순열인 이유는,

a0 a1 a2 a3

a0 a3 a2 a1

a1 a2 a0 a3

등의 경우를 모두 다른 경우로 보기 때문이다.

 

순열은 재귀에서 visited로 방문 체크를 한 뒤, 다음 뎁스로 넘어가고, 다시 현재 뎁스로 돌아오는 경우 방문 체크를 해제하고, 다음 인덱스를 방문한 뒤 다음 뎁스로 넘어가는 것을 반복하면 된다.

 

코드

import kotlin.math.*
var answer= 0
fun permutation(len : Int, result : IntArray, n : Int, arr : IntArray,visited : BooleanArray){

    if(len == n){
        var sum=0
        for(i in 0 until n-1){
            sum += abs(result[i]-result[i+1])
        }
        answer = max(answer,sum)
        return
    }
    for(i in 0 until n){
        if(visited[i]) continue
        result[len]=arr[i]
        visited[i]=true
        permutation(len+1,result,n,arr,visited)
        visited[i]=false
    }

}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val arr = br.readLine().split(' ').map{it.toInt()}.toIntArray()
    val visited= BooleanArray(n)

    permutation(0,IntArray(n),n,arr,visited)
    write("$answer")
    close()
}