[백준] 2961번 도영이가 만든 맛있는 음식(완전탐색 - DFS)[Kotlin - 코틀린]

백준 2961번 문제입니다. (solved.ac) 기준 실버 2 문제입니다.

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

2961번: 도영이가 만든 맛있는 음식

문제

문제 접근

신맛, 쓴맛의 속성을 갖는 재료가 n개 있습니다. 이 재료들을 사용하여 만든 요리의 신맛은 사용한 재료들의 신맛의 곱이고 쓴맛은 사용한 재료들의 쓴맛의 합입니다. n개의 재료를 가지고 있을 때 이 재료들을 사용하여 신맛과 쓴맛의 차이가 가장 작은 요리를 만들도록 하고 그 차이를 출력해주면 되는 문제입니다.

 

재료의 개수인 n의 범위가 1이상 10이하이고 모든 재료를 사용하였을 때 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수라고 조건이 주어졌기 때문에 충분히 완전탐색으로 풀 수 있습니다.

원소가 n개인 집합에서 멱집합(공집합 == (아무 원소도 포함하지 않은 집합) 을 포함한 부분집합)이 아닌 부분집합들을 구하여 신맛과 쓴맛을 계산하고 그 중 차이가 가장 작은 요리의 신맛, 쓴맛의 차이를 출력하면 되는 문제입니다.

 

1 ~ n개의 원소를 포함한 부분집합을 구하기 위하여 DFS를 활용하였습니다(조합).

DFS를 이용한 순열, 조합은 이 링크에 설명되어있습니다.

 

부분 집합을 구한 후 해당 재료들을 사용한 요리의 신맛, 쓴맛의 차를 구하여 최소의 차를 가질 수 있도록 갱신을 해주었습니다.
차를 구하는 과정에서는 절댓값을 사용하기위해 abs의 함수를 사용하지 않고 그냥 조건문을 사용하여 더 큰 값에서 작은 값을 뺄 수 있도록 하였습니다. 

정답 코드

val flavorList = mutableListOf<Pair<Int, Int>>()
val ingredientsCnt = readln().toInt()
val pickedList = mutableListOf<Pair<Int, Int>>()
var minDiffOfCook = 1000000000

fun main() {

    repeat(ingredientsCnt) {
        val curFlavor = readln().split(" ").map { it.toInt() }
        flavorList.add(Pair(curFlavor[0], curFlavor[1]))
    }
    
    for (depth in 1..ingredientsCnt) {
        subSet(0, depth, 0)
    }

    println(minDiffOfCook)

}

fun subSet(cnt: Int, depth: Int, beginWith: Int) {

    if (cnt == depth) {
        var curSourSum = 0
        var curBitterSum = 0
        pickedList.forEachIndexed { index, flavor ->
            if (index == 0) {
                curSourSum += flavor.first
                curBitterSum += flavor.second
            } else {
                curSourSum *= flavor.first
                curBitterSum += flavor.second
            }
        }

        var curDiffOfCook = 0
        if (curSourSum >= curBitterSum) {
            curDiffOfCook = curSourSum - curBitterSum
        } else {
            curDiffOfCook = curBitterSum - curSourSum
        }

        if (curDiffOfCook < minDiffOfCook) minDiffOfCook = curDiffOfCook
    }
    for (index in beginWith until ingredientsCnt) {
        pickedList.add(flavorList[index])
        subSet(cnt + 1, depth, index + 1)
        pickedList.removeAt(pickedList.lastIndex)
    }
}