백준 16198 에너지 모으기 Kotlin (순열)

문제 출처 : https://www.acmicpc.net/problem/16198

16198번: 에너지 모으기

문제

N개의 에너지 구슬이 일렬로 놓여 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
2. x번째 에너지 구슬을 제거한다.
3. Wx-1 × Wx+1의 에너지를 모을 수 있다.
4. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

간단한 순열 문제이다.

입력의 크기가 5라면, 0 < x <4, 즉 1,2,3을 여러 순서로 뽑는다.

이렇게 뽑은 셋으로 에너지 양을 계산해서 최댓값을 갱신하면 된다.

이는 visited로 구현했는데, 에너지 구슬을 뽑았을 때 배열에서 진짜 값을 빼는 게 아닌, visited를 true로 처리하여 제외시켰다. 아래 코드가 구슬 하나를 뽑았을 때 에너지를 계산하는 코드다.

fun findNext(idx: Int,n: Int): Int{
    var left = input[0]
    var right = input[n-1]
    for(i in idx -1 downTo 1){
        if(!visited[i]){
            left = input[i]
            break
        }
    }
    for(i in idx+1 until n-1){
        if(!visited[i]){
            right = input[i]
            break
        }
    }
    val next = left*right
    return next
}

 

코드

val br = System.`in`.bufferedReader()

fun getInt() = br.readLine().toInt()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
lateinit var input: IntArray
lateinit var visited: BooleanArray
var answer=0

fun findNext(idx: Int,n: Int): Int{
    var left = input[0]
    var right = input[n-1]
    for(i in idx -1 downTo 1){
        if(!visited[i]){
            left = input[i]
            break
        }
    }
    for(i in idx+1 until n-1){
        if(!visited[i]){
            right = input[i]
            break
        }
    }
    val next = left*right
    return next
}

fun permutation(idx: Int, result : Int, cnt: Int, n: Int){

    answer = answer.coerceAtLeast(result)
    if(cnt==n-2) return

    for(i in 1 until n-1){
        if(visited[i]) continue
        val next = findNext(i,n)
        visited[i] = true
        permutation(i,result + next,cnt+1,n)
        visited[i] = false
    }
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    val n = getInt()
    input = getIntList().toIntArray()
    visited = BooleanArray(n)

    //solve
    permutation(1,0,0,n)

    //output
    write("$answer")
    close()
}