1744번: 수 묶기 - Kotlin

1744번: 수 묶기

문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

 

나의 풀이

 이 문제는 그리디로 해결해야 하는 문제이다. 그리디 알고리즘은 정렬을 잘 사용하고 최적의 결과를 얻을 수 있게 데이터를 잘 정리하는 것이 핵심이다.

 나는 이 문제를 주어진 수열을 음수와 양수로 나누는 것 부터 진행하였다. 양수 배열은 숫자가 step으로 2칸씩 띄워가면서 진행하였다. 다만 여기서 생각해야 할 것은 2 * 1보다 2 + 1이 더 크다는 것이다. 그러므로 이어진 숫자가 둘 다 1이 아닐 때만 곱해주고 둘 중 하나가 1일때는 더해주는 식으로 양수 배열을 더하였다. 추가로 양수 배열의 크기가 홀수일 때는 최대 크기를 조절해주고 마지막 요소를 더해주는 조건을 추가 해주었다.

 

 음수 배열도 마찬가지이다. 음수와 음수를 곱하면 양수임으로 가장 작은 음수부터 곱하면서 더해주었다. 홀수일 때는 음수인 숫자가 하나 남게 된다. 이때 이전에 0이 있는지 체크를 했었는데, 만약 0이 있다면 음수와 곱해줘서 더하지 않아도 된다. 0이 없다면 하나 남은 음수를 더해줘야 한다.

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    val arr = Array(n) { readLine().toInt() }

    var plusArr = mutableListOf<Int>()
    var minusArr = mutableListOf<Int>()
    var zeroCnt = false

    arr.forEach {
        if (it == 0) {
            zeroCnt = true
        } else if (it < 0) {
            minusArr.add(it)
        } else {
            plusArr.add(it)
        }
    }

    plusArr.sortDescending()

    var ans = 0
    var plusSize = plusArr.size
    if (plusSize % 2 == 1) {
        plusSize -= 1
        ans += plusArr.last()
    }

    for (i in 0 until plusSize step 2) {
        if (plusArr[i] > 1 && plusArr[i + 1] > 1) {
            ans += plusArr[i] * plusArr[i + 1]
        } else {
            ans += plusArr[i] + plusArr[i + 1]
        }
    }

    minusArr.sort()
    var minusSize = minusArr.size
    if (minusSize % 2 == 1) {
        minusSize -= 1
        if (!zeroCnt)
            ans += minusArr.last()
    }

    for (i in 0 until minusSize step 2) {
        ans += minusArr[i] * minusArr[i + 1]
    }

    println(ans)
}