BOJ 14889 스타트와 링크

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

분류: 완전탐색

---

접근방식

짝수의 사람과 두 사람이 같은 팀일 때 능력치가 주어지고,

사람들을 두 팀으로 나눌 때, 능력치의 차이를 구하는 문제입니다.

핵심 포인트는 크게 두 가지로 볼 수 있습니다.

1. 사람들을 두 팀으로 나누기

2. 각 팀의 능력치를 구하기

주의할 점은 각 팀의 능력치를 구할 때 팀원 두 쌍의 능력치를 각각 모두 더해줘야 합니다.

만약 1, 3, 6이 한 팀이고 두 사람이 팀일 때 능력치를 Sij 라고 한다면,

S13 + S16
S31 + S36
S61 + S63

위 6가지 경우를 모두 더해줘야 합니다.

 

해결방법

팀을 나누는 건 3명을 뽑으면 나머지 팀은 자동으로 완성되므로 3명을 뽑을 때까지 재귀로 구현했습니다.

func makeTeam(team: Set<Int>, current: Int) {
    if current < members.count {
        makeTeam(team: team, current: current+1)
        var newTeam = team
        newTeam.insert(current)
        makeTeam(team: newTeam, current: current+1)
    }
}

for people in 0..<n/2 {
    makeTeam(team: Set<Int>(arrayLiteral: people), current: people+1)
}

 

팀 3명이 정해졌으면 각 팀의 능력치를 구해야 합니다. 
0부터 모든 멤버를 돌면서 우리 팀, 다른 팀을 나누면서
추가하기 전에 먼저 팀에 들어있는 사람과의 능력치를 구합니다.
최정 차이를 갖는 변수 하나를 두고 우리팀은 더하고 다른 팀은 빼서 절대값을 리턴합니다.

func getDifference(of team: Set<Int>) -> Int {
    var myTeam = [Int]()
    var otherTeam = [Int]()
    
    var difference = 0
    
    for member in 0..<n {
        if team.contains(member) {
            for t in myTeam {
                difference += members[member][t]
                difference += members[t][member]
            }
            myTeam.append(member)
        } else {
            for t in otherTeam {
                difference -= members[member][t]
                difference -= members[t][member]
            }
            otherTeam.append(member)
        }
    }
    return abs(difference)
}

 

배운점

이제 완전탐색 문제는 꽤 익숙해진 것 같다. 다른 분들은 더 빠르게 푸셨던데... 

더 빠른 방법도 고민해봐야겠다.