[백준/Swift] 14889번: 스타트와 링크

 

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

14889번: 스타트와 링크

 

이번 문제는 브루트포스/백트래킹으로 풀었다.

N/2 명의 경우의 수만 구하면 start 팀과 link 팀의 능력치를 구할 수 있다.

 

0~(n-1) 중 n/2개를 선택하면 되므로 이에 따른 백트래킹을 구현해 주었다.

일단, 따로 선수를 배열에 넣지 않고 선택한 선수를 visited 부울 배열에 true로 넣고 만약 n/2명을 선택했다면 

true인 애들은 start 팀에 능력치를 넣어준다. 여기서 for-in loop를 통해 true인 i, j와 j, i 값을 start에 더해준다.

그리고 나머지 선수는 link에 넣어주면 된다.

 

N과 M 시리즈에서 이 문제는 중복 x && 오름차순의 경우다.

 

{true, true, false, false}

{true, false, true, false}

{true, false, false, true}

{false, true, true, false}

{false, true, false, true}

{false, false, true, true}

 

 

import Foundation

let n = Int(readLine()!)!
var array = [[Int]]()
var answer = Int.max
var visited = [Bool](repeating: false, count: n+1)
for _ in 0..<n {
    array.append(readLine()!.split(separator: " ").map{ Int(String($0))! })
}

var list = [Int]()

func bt(_ count: Int, _ now: Int) {
    if count == n/2 {
        var start = 0
        var link = 0
        for i in 0..<n {
            for j in 0..<n {
                if visited[i] && visited[j] { start += array[i][j] }
                else if !visited[i] && !visited[j] {
                    link += array[i][j]
                }
            }
        }
        answer = min(answer, abs(start - link))
        return
    }
    
    for i in now..<n {
        visited[i] = true
        bt(count+1, i+1)
        visited[i] = false
    }
}

bt(0, 0)
print(answer)

 

 

백트래킹 문제는 조건을 잘 생각해 보는 게 중요한 것 같다. 중복원소가 가능한지, 순서가 있는지(오름차순, 비내림차순)

정신 차리고 문제 풀자!