BOJ: #14889 - 스타트와 링크

정확히 한 시간 걸려서 풀었다. 정답 코드 하단에 시간 초과, 메모리 초과 코드도 같이 첨부했다.

1. 일단, 메모리 초과가 났을 때는 모든 경우의 수를 2차원 배열로 저장해서 생기는 문제였다. 메모리 초과가 난 후에, 굳이 저장할 필요가 없다는 걸 깨달아서 저장하지 않고, 바로 점수 계산하는 식으로 변경했다.
2. 그리고 이렇게 변경하면서, 질문 게시판을 보니 전체 팀을 집합으로 만들어 놓고, n / 2의 조합을 구한 후에, 차집합을 구하는 식으로 링크 팀을 구하라는 이야기가 있어서 그것도 반영했다. 여기까지가 시간 초과 난 코드였다.
3. 도무지 해결책을 모르겠어서, PyPy3로도 실행해봤는데 역시나 시간초과였다. 다른 글을 찾아보니 대게, 시간 초과 난 코드들은 조합 구하는 함수가 비효율적이라는 답변을 봤다. 그래서 언젠가 저장해놨던, 다른 분의 조합 코드를 조금 수정해서 실행했더니 통과했다. 한마디로 내가 사용하고 있는 코드가 느리다는 것... 으아아아!
4. 아무튼 결국 풀었고... 앞으로는 이번에 사용한 조합 코드를 사용하는 걸로... 혼자 합의 봤다. 이것도 외울 수 있을 때까지 반복적으로 연습해서 작성해봐야지.

 

문제

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

 

내가 작성한 코드

Swift: 정답

let n = Int(readLine()!)!
let m = Int(n/2)
var score = [[Int]]()
var totalTeam = Set(Array(0..<n))
for _ in 0..<n {
    let line = readLine()!.split(separator: " ").map { Int(String($0))! }
    score.append(line)
}

var answer = 987654321

func cal(startTeam: [Int], linkTeam: [Int]) {
    var startTeamSum = 0
    var linkTeamSum = 0
    for i in 0..<m {
        for j in i+1..<m {
            startTeamSum += score[startTeam[i]][startTeam[j]] + score[startTeam[j]][startTeam[i]]
            linkTeamSum += score[linkTeam[i]][linkTeam[j]] + score[linkTeam[j]][linkTeam[i]]
        }
    }

    answer = min(answer, abs(startTeamSum - linkTeamSum))
}

func combination(of total: [Int], selectedCount: Int, current idx: Int, seletcted: [Int]) {
    if selectedCount == 0 {
        cal(startTeam: seletcted, linkTeam: Array(totalTeam.subtracting(Set(seletcted))))
    } else if idx == total.count {
        return
    } else {
        let new = seletcted + [total[idx]]
        combination(of: total, selectedCount: selectedCount-1, current: idx+1, seletcted: new)
        combination(of: total, selectedCount: selectedCount, current: idx+1, seletcted: seletcted)
    }
}

combination(of: Array(0..<n), selectedCount: m, current: 0, seletcted: [])

print(answer)

 

Swift: 시간 초과

let n = Int(readLine()!)!
let m = Int(n/2)
var score = [[Int]]()
var totalTeam = Set(Array(0..<n))
for _ in 0..<n {
    let line = readLine()!.split(separator: " ").map { Int(String($0))! }
    score.append(line)
}

var answer = 987654321

func cal(startTeam: [Int], linkTeam: [Int]) {
    var startTeamSum = 0
    var linkTeamSum = 0
    for i in 0..<m {
        for j in i+1..<m {
            startTeamSum += score[startTeam[i]][startTeam[j]] + score[startTeam[j]][startTeam[i]]
            linkTeamSum += score[linkTeam[i]][linkTeam[j]] + score[linkTeam[j]][linkTeam[i]]
        }
    }

    answer = min(answer, abs(startTeamSum - linkTeamSum))
}

var picked = [Int]()
var visited = Array(repeating: false, count: n)

func pick(toPick: Int) {
    if toPick == 0 {
        cal(startTeam: picked, linkTeam: totalTeam.subtracting(Set(picked)).sorted())
        return
    }
    for i in 0..<n {
        if visited[i] {
            continue
        }
        visited[i] = true
        picked.append(i)
        pick(toPick: toPick - 1)
        picked.removeLast()
        visited[i] = false
    }
}

pick(toPick: m)

print(answer)

 

Swift: 메모리 초과

let n = Int(readLine()!)!
var score = [[Int]]()

for _ in 0..<n {
    let line = readLine()!.split(separator: " ").map { Int(String($0))! }
    score.append(line)
}

var teams = [[Int]]()
var picked = [Int]()
var visited = Array(repeating: false, count: n)
func pick() {
    if picked.count == n {
        teams.append(picked)
        return
    }
    for i in 0..<n {
        if visited[i] {
            continue
        }
        visited[i] = true
        picked.append(i)
        pick()
        picked.removeLast()
        visited[i] = false
    }
}

pick()

var answer = 987654321
for team in teams {
    var startTeam = 0
    for i in 0..<n/2 {
        for j in i+1..<n/2 {
            startTeam += score[team[i]][team[j]]
            startTeam += score[team[j]][team[i]]
        }
    }
    var linkTeam = 0
    for i in n/2..<n {
        for j in i+1..<n {
            linkTeam += score[team[i]][team[j]]
            linkTeam += score[team[j]][team[i]]
        }
    }
    answer = min(answer, abs(startTeam - linkTeam))
}

print(answer)