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

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

10819번: 차이를 최대로

문제 풀이

1. 주어진 배열 A 를 반복을 허락하지 않고 DFS 를 이용하여 나올 수 있는 배열의 경우를 구한다.

2. 1번에서 구해진 각 배열에서 "차이의 최대 값"을 구한다.

코드

import java.io.*

var answer10819 = Int.MIN_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val number = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    val visit = BooleanArray(N) { false }
    val result = IntArray(N) { 0 }
    dfs(N, number, visit, result, 0)
    println(answer10819)
}

fun dfs(n: Int, num: IntArray, visit: BooleanArray, ret: IntArray, depth: Int) {
    if (depth == n) {
        // 최대 값 구하기
        answer10819 = Math.max(answer10819, getSum(n, ret))
        return
    }

    for (i in 0 until n) {
        if (!visit[i]) {
            visit[i] = true
            ret[depth] = num[i]
            dfs(n, num, visit, ret, depth + 1)
            visit[i] = false
        }
    }
}

fun getSum(n: Int, ret: IntArray): Int {
    var result = 0

    for (i in 0 until (n -1) ) {
        result += Math.abs(ret[i] - ret[i + 1])
    }

    return result
}