[백준][코틀린] 14889 스타트와 링크

문제 내용

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

i \ j	1	2	3	4
1		1	2	3
2	4		5	6
3	7	1		2
4	3	4	5

스타트 팀: S12 + S21 = 1 + 4 = 5
링크 팀: S34 + S43 = 2 + 5 = 7
1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

스타트 팀: S13 + S31 = 2 + 7 = 9
링크 팀: S24 + S42 = 6 + 4 = 10
축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입력	예제 출력
4 0 1 2 3 4 0 5 6 7 1 0 2 3 4 5 0	0
6 0 1 2 3 4 5 1 0 2 3 4 5 1 2 0 3 4 5 1 2 3 0 4 5 1 2 3 4 0 5 1 2 3 4 5 0	2
8 0 5 4 5 4 5 4 5 4 0 5 1 2 3 4 5 9 8 0 1 2 3 1 2 9 9 9 0 9 9 9 9 1 1 1 1 0 1 1 1 8 7 6 5 4 0 3 2 9 1 9 1 9 1 0 9 6 5 4 3 2 1 9 0	1

문제 풀이

조합으로 가능한 팀의 조합을 뽑아두고, 그 팀을 A, 나머지 인원으로 꾸린 B로 두고 팀의 능력치 합을 비교했다. 비교치가 가장 작은 것을 result에 저장해서 결과를 출력했다.

여기서 신경 쓴 부분은 총 2가지 이다.

1번째

makeTeam 에서 팀을 뽑을때 조합에서 절반만 뽑기. 조합을 나열하면 딱 반으로 접으면 모든 인원이 나온다. 이게 무슨 말인지 설명해보자면..

따라서, 우리는 조합의 절반만큼만 구하면 된다. 그리고 첫 자리는 언제나 1이다. 따라서 makeTeam의 첫 시작은 depth = 1( 배열의 1번째 즉, array[1]자리)부터 시작해서 구하면 된다~~~ 

2번째

calculatorPower 에서 팀의 능력치를 계산할 때 people2는 people1 다음부터 확인한 것

예를 들어 총 4명일때 팀 A에 0, 1이 포함되어있다.

근데, 만약에 아래와 같이 for문을 돌리면, <0, 1>이 한팀인 것과 <1, 0>이 한팀인 것과 해서 값이 2배로 불어나는 기적을 볼 수 있을 것이다.

for (people1 in 0 until n) {
        for (people2 in 0 until n) {
        // ...
       	}
}

그래서 people2는 people1 + 1 until n으로 범위를 지정해주었다. 

</>̆̈ 코드

import java.io.BufferedReader
import java.io.InputStreamReader

private var n = 0
private var result = Int.MAX_VALUE
private lateinit var company: List<List<Int>>

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    n = br.readLine().toInt()
    company = List(n) {br.readLine().split(" ").map { it.toInt() }}

    makeTeam()
    print(result)
}

private fun makeTeam(depth: Int = 1, idx: Int = 1, peoples: IntArray = IntArray(n / 2)) {
    if (depth == n / 2) { calculatorPower(peoples); return }

    for (index in idx until n) {
        peoples[depth] = index
        makeTeam(depth + 1, index + 1, peoples )
    }
}

private fun calculatorPower(peoples: IntArray) {
    var teamA = 0; var teamB = 0
    val isTeamA = BooleanArray(n)

    for (people in peoples) isTeamA[people] = true

    for (people1 in 0 until n) {
        for (people2 in people1 + 1 until n) {
            if (isTeamA[people1] == isTeamA[people2]) {
                if (isTeamA[people1]) teamA += company[people1][people2] + company[people2][people1]
                else teamB += company[people1][people2] + company[people2][people1]
            }
        }
    }
    result = minOf(result, kotlin.math.abs(teamA-teamB))
}

링크

14889번: 스타트와 링크