[Swift] 14889 스타트와 링크 (조합)

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

14889번: 스타트와 링크

 

생각

스타트 팀과 링크 팀 두개의 팀으로 나누기 때문에 두개의 팀 모두 인원은 전체인원 / 2 명

-> 조합으로 경우의 수를 모두 구해서 팀원의 능력치가 가장 작은 방법을 구합니다.

 

능력치를 구하는 방법은 같은 팀일 때만 (여기서는 visited 배열을 사용) 능력치를 더해주었습니다.

 

 

 

조합문제를 Swift로 푸는 것은 처음인데 알고리즘을 푸는 방법은 동일해서 코드도 언어만 다르지 동일

백준문제에서도 요즘은 Swift로 풀어도 시간초과가 잘 안나는 것 같습니다 ㅎ.ㅎ

 

시간초과가 났던 이유는 조합을 구할 때 다음 현재 index의 다음번부터 조합을 구했어야 했는데

count의 다음번을 for문의 시작으로 넣었기 때문이었습니다..

 

 

전체코드

import Foundation

// input
let N = Int(readLine()!)!

var power = [[Int]](Array(repeating: Array(repeating: 0, count: N+1), count: N+1))

// input
for i in 1...N {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    for j in 1...N {
        power[i][j] = input[j-1]
    }
}

// 변수 선언
let memberCount = N/2
var startPower = 0, linkPower = 0, result = Int.max
var visited = [Bool](Array(repeating: false, count: N+1))

// 조합짜기
func makeTeam(_ start: Int, _ count: Int) {
    if count == memberCount + 1 {
        getDiffPower()
        return
    }
    
    for i in start...N {    // 시간초과의 원인
        if !visited[i] {
            visited[i] = true
            makeTeam(i, count + 1)
            visited[i] = false
        }
    }
}

// 팀의 능력치 차이 구하기
func getDiffPower() {
    startPower = 0
    linkPower = 0
    
    for i in 1...N {
        for j in i...N {
            if visited[i] && visited[j] {
                startPower += power[i][j] + power[j][i]
            }
            else if !visited[i] && !visited[j] {
                linkPower += power[i][j] + power[j][i]
            }
        }
    }
    result = min(result, abs(startPower - linkPower))
}

makeTeam(1, 1)
print(result)