10819번: 차이를 최대로

문제 풀이 아이디어

수열의 최대 길이는 8로 모든 경우를 구해서 계산해도 시간초과가 나오지 않을 크기 입니다.

문제를 처음 보면 순열을 구해서 계산하는 방법을 떠올릴 수도 있지만 Swift로 순열을 구하는 것은 번거로운 일이므로 간단하게 dfs를 통해서 모든 경우의 수를 탐색하는 방법으로 해봅시다.

코드

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

// 최댓값을 구할 때 최초값은 Int.min
var ans = Int.min

// dfs 구현
    //👉 합을 계산할 때 now가 필요함!
func dfs(now: Int, depth: Int, sum: Int) {
    // 깊이 = 수열의 길이일 때 최댓값과 비교하기
    if depth == N {
        ans = max(ans, sum)
        return
    }
    
    // 다음에 올 index 탐색
    for i in 0..<N {
        if !visited[i] { //👉 아직 방문하지 않은 index라면
            let newSum = sum + abs(array[now] - array[i]) //👉 계산해서 현재합에 더하고
            visited[i] = true //👉 방문체크하고
            dfs(now: i, depth: depth + 1, sum: newSum) //👉 dfs
            visited[i] = false //👉 dfs한 이후에는 방문체크 해제
        }
    }
}

// 시작하는 index가 N가지 있으므로 반복문으로 dfs 돌리기
for i in 0..<N {
    visited[i] = true
    dfs(now: i, depth: 1, sum: 0)
    visited[i] = false
}

print(ans)