백준 10819 차이를 최대로

출처: www.acmicpc.net/problem/10819

분류: 완전탐색, 순열

---

접근방식

n이 최대 8밖에 되지 않아 가능한 배열 조합을 모두 구해서 주어진 식대로 계수의 최댓값을 계산했습니다.

주어진 예제에서는

[8, 15, 1, 20, 4, 10]

경우에 가장 큰 최댓값이 나오는데 어떤 경우에 최대가 나오는 특별한 규칙이 있는건지는 잘 모르겠습니다.. ㅠㅠ

순열을 오랜만에 해서 처음에는 배열을 만들어가고 해당 수를 넣었는지 체크하는 bool 배열을 만들고...
굉장히 비효율적으로 풀었었네요 ㅠㅠ

덕분에 오랜만에 순열을 다시 복습해볼 수 있어서 좋았네요 :) 

전통적인 순열은 스왑을 통해 백트래킹 방식으로 구할 수 있습니다.

앞에서부터 해당 자리에 들어갈 수를 채워넣어가는 방식으로

바꿀 자리의 인덱스와 바꿔서 재귀호출을 하고 뒤에 다시 원래대로 되돌려 놓는 방식으로 구현이 가능합니다.

for changing in curr..<n {
  arr.swapAt(curr, changing)
  perm(&arr, curr+1)
  arr.swapAt(curr, changing)
}

 

조금 더 자세한 설명은 여기서 

 

해결방법

import Foundation

let n = Int(readLine()!)!
var numbers = readLine()!.split(separator: " ").map { Int(String($0))! }
var maxValue = 0

func diffSum(_ arr: [Int]) -> Int {
    var sum = 0
    for idx in 0..<arr.count-1 {
        sum += abs(arr[idx] - arr[idx+1])
    }
    return sum
}

func perm(_ arr: inout [Int], _ curr: Int) {
    guard curr < n else {
        let sum = diffSum(arr)
        if sum > maxValue {
            print(arr)
            maxValue = sum
        }
        return
    }
    
    for changing in curr..<n {
        arr.swapAt(curr, changing)
        perm(&arr, curr+1)
        arr.swapAt(curr, changing)
    }
}

perm(&numbers, 0)
print(maxValue)

 

처음에 풀었던 비효율적인 풀이 😅

import Foundation

let n = Int(readLine()!)!
var numbers = readLine()!.split(separator: " ").map { Int(String($0))! }
var maxValue = 0

func diffSum(_ arr: [Int]) -> Int {
    var sum = 0
    for idx in 0..<arr.count-1 {
        sum += abs(arr[idx] - arr[idx+1])
    }
    return sum
}

func orderNumbers(_ curr: [Int], _ used: [Bool]) {
    guard curr.count != n else {
        let sum = diffSum(curr)
        if sum > maxValue {
            maxValue = sum
        }
        return
    }
    
    for (idx, num) in numbers.enumerated() where !used[idx] {
        var newArr = curr
        var newUsed = used
        newArr.append(num)
        newUsed[idx] = true
        orderNumbers(newArr, newUsed)
    }
}

orderNumbers([], [Bool](repeating: false, count: n))
print(maxValue)

 

배운점

순열 복습. 연습 또 연습 연습만이 살길....