백준 19942번
https://www.acmicpc.net/problem/19942

문제

---

생각하기

---

• 백트래킹을 통해서 모든 경우의 수를 탐색하여 정답을 찾는 문제이다.

• 생각보다(?) 시간이 널널 한 것 같다

동작

private fun DFS(index: Int, indexList: ArrayList<Int>) {
    if (index <= N) {
        if (checkMin(indexList)) {
            var sum = 0
            indexList.forEach {
                sum += arr[it].cost!!
            }

            if (result > sum) {
                result = sum
                resultList = ArrayList()
                resultList.addAll(indexList)
            }
        }

        if (index == N) {
            return
        }
    }

    // 샀을 때,
    indexList.add(index)
    DFS(index + 1, indexList)

    // 사지 않았을 때
    indexList.removeLast()
    DFS(index + 1, indexList)

} // End of DFS

식재료를 샀을 때 가지와 사지 않았을 때의 가지로 뻗어나가서 모든 경우의 수를 탐색할 수 있다.

indexList에 index를 add()로 저장하여 해당 식재료를 구매했다는 것으로 해주고

사지 않았을 때는 위에서 샀던 식재료를 빼는 방식 poll()을 통해서 빼서 2가지로 뻗어 나간다.

그리고 N이 되지 않았을 때도 최소한의 조건을 도달할 수 있으므로
if(index <= N)의 조건으로 재귀가 한번 실행될 때 마다 조건을 체크하도록 했다.

코드

---

Kotlin

import java.util.*
import java.io.*
import java.lang.StringBuilder


private var N = 0
private var result = Integer.MAX_VALUE
private lateinit var resultList: LinkedList<Int>
private val min = Food(0, 0, 0, 0)
private val arr = Array(16) { Food() }

private data class Food(
    var protein: Int = 0,
    var fat: Int = 0,
    var carbo: Int = 0,
    var vitamin: Int = 0,
    var cost: Int? = 0
) {
    constructor(protein: Int, fat: Int, carbo: Int, vitamin: Int) : this(0, 0, 0, 0, 0)
}

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))

    N = br.readLine().toInt()
    var st = StringTokenizer(br.readLine())
    min.protein = st.nextToken().toInt()
    min.fat = st.nextToken().toInt()
    min.carbo = st.nextToken().toInt()
    min.vitamin = st.nextToken().toInt()

    for (i in 0 until N) {
        st = StringTokenizer(br.readLine())
        arr[i] = Food(
            st.nextToken().toInt(),
            st.nextToken().toInt(),
            st.nextToken().toInt(),
            st.nextToken().toInt(),
            st.nextToken().toInt(),
        )
    }

    val indexList = LinkedList<Int>()
    DFS(0, indexList)

    if (result == Integer.MAX_VALUE) {
        println(-1)
        return
    }

    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()

    sb.append(result).append('\n')
    resultList.sort()
    resultList.forEach {
        sb.append(it + 1).append(' ')
    }

    bw.write(sb.toString())
    bw.close()
} // End of main

private fun DFS(index: Int, indexList: LinkedList<Int>) {
    if (index <= N) {

        if (checkMin(indexList)) {
            var sum = 0
            indexList.forEach {
                sum += arr[it].cost!!
            }

            if (result > sum) {
                result = sum
                resultList = LinkedList()
                resultList.addAll(indexList)
            }
        }

        if (index == N) {
            return
        }
    }


    // 샀을 때,
    indexList.offerFirst(index)
    DFS(index + 1, indexList)

    // 사지 않았을 때
    indexList.pollFirst()
    DFS(index + 1, indexList)

} // End of DFS

// 최소 조건을 모두 만족하는지 체크하는 메소드
private fun checkMin(indexList: LinkedList<Int>): Boolean {

    var sum = Food()
    indexList.forEach {
        val temp = arr[it]

        sum.protein += temp.protein
        sum.fat += temp.fat
        sum.carbo += temp.carbo
        sum.vitamin += temp.vitamin
    }

    if (sum.protein >= min.protein && sum.fat >= min.fat && sum.carbo >= min.carbo && sum.vitamin >= min.vitamin) return true

    return false
} // End of checkMin