문제
N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.
|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
입력
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
출력
첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.
풀이
N의 최대가 8이므로 전부다 체크하더라도 크게 상관이 없을것 같아, 모두 확인해서 최대값을 찾았다.
코드
import kotlin.math.abs
import kotlin.math.max
var N : Int? = null
var A : List<Int>? = null
var ans :Int? = null
fun main()
{
N = readln().toInt()
A = readLine()!!.split(' ').map { it.toInt() }
var check = BooleanArray(N!!, {false})
var save = IntArray(N!!, {0})
ans = 0
dfs(0,check,save)
System.out.println(ans)
}
fun cal(save:IntArray) : Int
{
var sum = 0
for(i in 1..save.size-1)
{
sum += abs(save[i-1] - save[i])
}
return sum
}
fun dfs(cnt : Int, check:BooleanArray,save : IntArray)
{
if (cnt == N) {
ans = max(ans!!, cal(save))
}
else {
for(i in 0..N!!-1) {
if(!check!![i]){
check!![i] = true
save[cnt] = A!![i]
dfs(cnt+1, check, save)
check!![i] = false
}
}
}
}
'백준 > bfs dfs' 카테고리의 다른 글
백준 [16234] kotlin (1) | 2023.01.10 |
---|---|
백준 [4485] kotlin (0) | 2023.01.06 |
백준 14502 [kotlin] (0) | 2022.07.07 |
백준 3055 [kotlin] (0) | 2022.07.06 |
백준 14442 [kotlin] (0) | 2022.07.01 |