BOJ-10819 차이를 최대로 Swift

문제

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

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

입력

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

출력

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

내가 푼 풀이

- 백트래킹을 이용해서 주어진 A배열 순서의 모든 경우의수를 구해서 최대값을 갱신한다.

 

import Foundation

//입력받기
let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var result = 0
var visited = Array(repeating: false, count: N)

// DFS 백트래킹
func dfs(count: Int, nums: [Int]) {
    if count == N {
        result = max(result, sum(nums: nums))
        return
    }
    
    for i in 0..<N {
        if !visited[i] {
            visited[i] = true
            dfs(count: count+1, nums: nums + [arr[i]])
            visited[i] = false
        }
    }
}

// 합산
func sum(nums: [Int]) -> Int{
    var sum = 0
    for i in 0..<nums.count-1 {
        sum += abs(nums[i] - nums[i+1])
    }
    return sum
}

dfs(count: 0, nums: [])
print(result)