[백준][코틀린][16198] 에너지 모으기

https://www.acmicpc.net/problem/16198

16198번: 에너지 모으기

문제 풀이

1. 구슬의 무게를 저장하는 리스트 W 를 선언한다.

2. 구슬을 두 번째 부터 (마지막 - 1)번째 까지 모두 탐색하는 DFS 를 수행한다.

3. X로 선택될 경우 리스트 W 에서 제거한다. 이때 DFS 결과가 return 되어 다음 코드가 수행될 때 제거된 X 를 W 에 다시 업데이트 하는 로직을 처리한다.

코드

import java.io.*

private var result = Int.MIN_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val W = br.readLine().split(" ").map { it.toInt() }.toMutableList()

    dfs(N, W, 0)
    println(result)
}

private fun dfs(N: Int, W: MutableList<Int>, sum: Int) {
    //println("W size = ${W.size}")
    // 처음과 마지막 구슬만 남았으므로 에너지 양을 계산한다.
    if (W.size == 2) {
        result = Math.max(result, sum)
        return
    }

    for (i in 1 until W.size - 1) {
        //println("W[$i] = ${W[i]}")
        val marble = W[i]
        W.removeAt(i)
        val energy = W[i - 1] * W[i]
        //println("sum = $sum, $energy, $marble, $i")
        dfs(N, W, sum + energy)
        // 제거된 구슬을 다시 원복한다.
        W.add(i, marble)
    }
}