백준 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)
의 조건으로 재귀가 한번 실행될 때 마다 조건을 체크하도록 했다.
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