[백준] 2961번: 도영이가 만든 맛있는 음식 - Kotlin[코틀린]

문제

 

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

 

---

풀이

 

 백트래킹을 사용하여 해결할 수 있다. 백트래킹은 가능한 모든 경우의 수를 탐색하면서 답을 찾는 알고리즘으로 재귀 함수를 이용한다.

 

 재귀 함수에서는 현재 선택한 재료로 만들어진 음식의 신맛과 쓴맛을 계산하고, 두 맛의 차이의 최소값을 갱신한다. 이후 다음 재료를 선택하고 다시 재귀적으로 함수를 호출한다. 선택한 재료는 방문 처리를 하여 중복 선택을 방지한다.

 

 모든 가능한 조합을 탐색한 후에 최소값을 출력한다.

 

---

코드

 

import kotlin.math.abs

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val arr = Array(num){ br.readLine().split(' ').map { it.toInt() } }
    val visited = BooleanArray(num)
    var min = Int.MAX_VALUE

    fun check(sour: Int, bitter: Int) {
        min = minOf(min, abs(sour-bitter))

        for(i in 0 until num) {
            if(visited[i]) continue
            visited[i] = true
            check(sour*arr[i][0], bitter+arr[i][1])
            visited[i] = false
        }
    }

    for(i in 0 until num) {
        visited[i] = true
        check(arr[i][0], arr[i][1])
        visited[i] = false
    }

    bw.write("$min")
    bw.flush()
    bw.close()
    br.close()
}