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

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

10819번: 차이를 최대로

난이도 : 실버 2
태그 : 브루트포스, 백트래킹

 

 

설명

배열의 순서를 적절히 섞어 위 식의 최댓값을 찾는 문제였습니다.

처음에는 위 식을

|A[0] - A[1]| + |A[2] - A[3]| 과 같이 두 식의 차이의 절대값 인줄 알고

그리디로 접근하면 되겠지? 싶었는데

|A[0] - A[1]| + |A[1] - A[2]| 였습니다 ㅎㅎ; 😭

 

흠... 그럼 두 번째 방법으로,

백트래킹으로 모든 경우의 수를 탐색하는 방법을 생각해봤습니다.

각 숫자로 만들 수 있는 모든 순열을 만들고,

이를 위 식에 대입해보겠습니다.

 

 

 

 

소스코드

import java.util.*
import kotlin.math.abs

var n = 0
var max = 0
lateinit var arr: Array<Int>
lateinit var visited: Array<Boolean>
lateinit var arrIdx: Array<Int>

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    val st = StringTokenizer(readLine())
    arr = Array(n) { st.nextToken().toInt() }
    visited = Array(n) { false }
    arrIdx = Array(n) { -1 }

    backTracking(0)
    println(max)
}

fun backTracking(idx: Int) {
    if (idx == n) {
        var sum = 0
        for (i in 0 until n - 1) {
            sum += abs(arr[arrIdx[i]] - arr[arrIdx[i + 1]])
        }
        max = maxOf(max, sum)
        return
    }

    for (i in 0 until n) {
        if (!visited[i]) {
            visited[i] = true
            arrIdx[idx] = i
            backTracking(idx + 1)
            visited[i] = false
        }
    }
}

 

 

배열의 모든 순서를 찾는게 목적이므로,

각 배열은 중복 방문이 안됩니다. 따라서 visited 배열을 두어 방문 여부를 체크합니다.

arrIdx는 각 배열이 몇 번째 배열의 값을 갖고 올지 담고있는 배열입니다.

0~n-1 까지 arrIdx에 모든 순열을 담고,

backTracking의 Depth가 n까지 도달하면,

위 식을 대입하여 max를 업데이트 합니다.