백준 - 2961 도영이가 만든 맛있는 음식 (코틀린)

[문제]

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

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

[풀이]

완전탐색 문제이다. 재귀를 이용해서 푸는데 음식을 저장한 배열의 인덱스를 재귀의 인수로 넘겨주면서 해당하는 인덱스의 음식을 더하거나 더하지 않거나 하여 재귀를 돌리고 인덱스가 음식의 수와 같아지는 조건에 음식들의 신 맛과 쓴 맛을 구하여 차이가 가장 작은 값을 구하면 된다.

시간복잡도 : O(2^N)

[코드]

import java.util.ArrayList
import kotlin.math.absoluteValue

private var n = 0
private lateinit var foods : Array<Pair<Long,Long>>
private lateinit var selected : ArrayList<Pair<Long,Long>>
private var answer = Long.MAX_VALUE
fun main() {
    val br = System.`in`.bufferedReader()
    n = br.readLine().toInt()
    foods = Array(n){ Pair(0L,0L) }
    selected = arrayListOf()
    repeat(n){
        br.readLine().split(" ").map { it.toLong() }.apply {
            foods[it] = Pair(this[0],this[1])
        }
    }
    rec(0)
    println(answer)
}
private fun rec(idx : Int){
    if(idx == n){
        if(selected.size >= 1){
            var s = 1L
            var b = 0L
            selected.forEach {
                s *= it.first
                b += it.second
            }
            answer = Math.min((s-b).absoluteValue,answer)
        }
    }
    else {
        selected.add(foods[idx])
        rec(idx+1)
        selected.removeLast()

        rec(idx+1)
    }
}