[コートリン]ペクジュン15686号:チキン出前-三星ソフトウェア能力試験出題

に答える

質問ではM社のフライドチキン店しか運営できないことを説明しましただからbacktrackingを利用してM個のフライドチキン店を繰り返し抽出しない場合、数量を求め、それぞれの状況に対してフライドチキンの距離を求めればよい.

M個のフライドチキン店のコードを重複なく抽出

繰り返さない場合、start変数を使用することが重要です.そうでないとタイムアウトになります.

fun selectChickenStore(start: Int, countSelected: Int, M: Int) {
    if (countSelected == M) {
        answer = min(calcChickenDst(), answer)
        return
    }

    for (i in start until chickenList.size) {
        selectedChickenStoreList.push(chickenList[i])
        selectChickenStore(start + 1, countSelected + 1, M)
        selectedChickenStoreList.pop()
    }
}

フライドチキン距離計算コード

fun calcChickenDst(): Int {
    var sum = 0
    houseList.forEach { house ->
        var minDst = Int.MAX_VALUE
        selectedChickenStoreList.forEach { chicken ->
            val dst = abs(house.r - chicken.r) + abs(house.c - chicken.c)
            minDst = min(dst, minDst)
        }
        sum += minDst
        if (sum > answer) return Int.MAX_VALUE
    }
    return sum
}

Source Code

package 삼성SW역량테스트.`15686번_치킨배달`

import java.util.Stack
import kotlin.math.abs
import kotlin.math.min

val chickenList = ArrayList<Dot>()
val houseList = ArrayList<Dot>()
val selectedChickenStoreList = Stack<Dot>()
var answer = Int.MAX_VALUE
fun main() {
    val (N, M) = readln().split(" ").map { it.toInt() }

    for (i in 0 until N) {
        val str = readln().split(" ").map { it.toInt() }
        for (j in 0 until N) {
            val obj = str[j]
            if (obj == 2) {
                chickenList.add(Dot(i, j))
            } else if (obj == 1) {
                houseList.add(Dot(i, j))
            }
        }
    }
    selectChickenStore(0, 0, M)
    println(answer)
}
fun selectChickenStore(start: Int, countSelected: Int, M: Int) {
    if (countSelected == M) {
        answer = min(calcChickenDst(), answer)
        return
    }

    for (i in start until chickenList.size) {
        selectedChickenStoreList.push(chickenList[i])
        selectChickenStore(start + 1, countSelected + 1, M)
        selectedChickenStoreList.pop()
    }
}
fun calcChickenDst(): Int {
    var sum = 0
    houseList.forEach { house ->
        var minDst = Int.MAX_VALUE
        selectedChickenStoreList.forEach { chicken ->
            val dst = abs(house.r - chicken.r) + abs(house.c - chicken.c)
            minDst = min(dst, minDst)
        }
        sum += minDst
        if (sum > answer) return Int.MAX_VALUE
    }
    return sum
}
data class Dot(val r: Int, val c: Int)