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

문제

---

생각하기

---

• 만들 수 있는 조합을 통해서 완전 탐색을 하면 되는 간단한 문제였다.

• 조합의 최대치가 정해져 있지 않았기 때문에 LinkedList를 사용해서 조합을 넣고 빼고 했다.

동작

코드

---

Kotlin

import java.io.*
import java.util.*

// variables
private lateinit var br: BufferedReader

// input
private var N = 0
private var ans = Int.MAX_VALUE

private lateinit var arr: Array<Taste>
private lateinit var isVisited: BooleanArray
private var comb: MutableList<Taste> = ArrayList()

private data class Taste(var sour: Int, var bitter: Int)

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val sb = StringBuilder()

    input()

    DFS(0, 0)

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

private fun DFS(depth: Int, idx: Int) {
    if (depth != 0) {
        var sSum = 1
        var bSum = 0
        comb.forEach {
            sSum *= it.sour
            bSum += it.bitter
        }

        ans = Math.min(ans, Math.abs(sSum - bSum))

        if (depth == N) {
            return
        }
    }

    for (i in idx until N) {
        if (isVisited[i]) continue

        isVisited[i] = true
        comb.add(arr[i])
        DFS(depth + 1, i)
        comb.removeAt(depth)
        isVisited[i] = false
    }
} // End of DFS

private fun input() {
    N = br.readLine().toInt()

    arr = Array(N) { Taste(0, 0) }
    isVisited = BooleanArray(N)

    for (i in 0 until N) {
        val st = StringTokenizer(br.readLine())
        arr[i].sour = st.nextToken().toInt()
        arr[i].bitter = st.nextToken().toInt()
    }
} // End of input