[BOJ/Silver 2] 백준 28447 마라탕 재료 고르기(Kotlin)

문제 링크

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

28447번: 마라탕 재료 고르기

 

문제

하얔이는 마라탕에 여러 재료를 넣어 먹는 것을 좋아한다. 하지만 마라탕에 항상 많은 재료를 넣는다고 맛있는 것은 아니다. 마라탕은 각 재료마다 궁합이 존재해서 같이 넣으면 맛있는 재료도 있고 그렇지 않은 경우도 있다. 여기서 하얔이는 고민에 빠졌다.

대체 어떻게 해야 K개의 재료를 넣었을 때 마라탕의 맛을 최대로 할 수 있는거지?

 C{i, j}를 재료 i와 재료 j를 같이 넣었을 때의 궁합이라 하자. 마라탕의 맛은 마라탕에 들어간 모든 재료 쌍의 궁합의 합이다. 고른 재료의 그룹을 G라고 했을 때 마라탕의 맛을 수식으로 표현하면 다음과 같다.

 

가여운 하얔이를 위해 재료를 K개만 사용했을 때의 최대의 마라탕의 맛을 구해보자.

 

입력

첫째 줄에 마라탕 재료의 수 N(1 ≤ N ≤ 10), 고를 재료의 수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다.

이후, N개의 줄에 걸쳐 i + 1번 줄에 재료 i와 다른 재료들의 궁합을 나타내는 수열 C{i, 1}, C{i, 2}, ..., C{i,N}이 공백으로 구분되어 정수로 주어진다. (−1,000 ≤ C{i, j} ≤ 1,000)

단, (C{i, i} = 0; C{i, j} = C{j, i})

 

출력

첫째 줄에 K개의 재료만 사용한 마라탕의 맛의 최댓값을 출력한다.

 

예제 입력 1

4 3
0 1 2 3
1 0 -2 6
2 -2 0 5
3 6 5 0

예제 출력 1

10

재료 1, 2, 4를 고르면 C{1, 2} = 1, C{1, 4} = 3, C{2, 4} = 6으로 최대인 10이 된다.

예제 입력 2

4 1
0 1 2 3
1 0 -2 6
2 -2 0 5
3 6 5 0

예제 출력 2

0

재료를 하나만 넣으면 궁합이 없으므로 마라탕의 맛은 0이 된다.

 

알고리즘 분류

• 백트래킹

 

풀이

N개의 재료 중에서 K개를 고를 수 있는 경우의 수를 탐색하면서 각 재료들의 궁합의 합의 최댓값을 구한다.

 

코드

import java.util.*
import kotlin.math.max

const val MIN = -1e9
var visited: Array<Boolean> = arrayOf()
var answer = MIN.toInt()

fun dfs(depth: Int, selected: Array<Int>, c: Array<Array<Int>>, k: Int) {
    if (depth == k) {
        var temp = 0
        for (i in selected.indices) {
            for (j in i + 1 until selected.size) {
                temp += c[selected[i]][selected[j]]
            }
        }
        answer = max(answer, temp)
        return
    }

    for (i in visited.indices) {
        if (!visited[i]) {
            visited[i] = true
            dfs(depth + 1, selected.plus(i), c, k)
            visited[i] = false
        }
    }
}

fun main() = with(Scanner(System.`in`)) {
    val a = nextLine().split(' ')
    val n = a[0].toInt()
    val k = a[1].toInt()
    var c: Array<Array<Int>> = arrayOf()
    for (i in 0 until n) {
        visited = visited.plus(false)
        val s = nextLine().split(' ')
        var arr: Array<Int> = arrayOf()
        for (sIdx in s.indices) {
            arr = arr.plus(s[sIdx].toInt())
        }
        c = c.plus(arr)
    }
    dfs(0, arrayOf(), c, k)
    println(answer)
}