백준 1744 수 묶기

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

딱 보기에 해볼만 해 보이지만, 예외 케이스에 대한 처리가 상당히 까다로운 문제였다.

길이가 최대 50인 수열이 주어지고, 각 수마다 최대 1회 묶을 수 있다.
수열의 모든 원소를 더한 합을 구하는데, 만약 두 수가 묶여 있다면 두 수는 곱해서 더한다.

수열의 합이 최대가 되도록 묶은 후의 합을 출력한다.

일단 내림차순 정렬은 필수라고 생각하고, 주어진 수열의 케이스를 나누어 보며 어떻게 처리할 지 생각해 보았다.

1. 양수만으로 주어지는 경우 ex) {5, 4, 3, 2, 1}
2. 음수만으로 주어지는 경우 ex) {-1, -2, -3, -4, -5}
3. 섞여서 주어지는 경우 ex) {3, 2, 1, -1, -2}

그리고 수열의 원소 개수에 따라서도 생각해 보았다.

1. 수열의 크기가 짝수인 경우 - 모든 수들이 묶일 수 있다
2. 수열의 크기가 홀수인 경우 - 모든 수들이 묶일 수 없다.

먼저 가장 간단한, 수열의 크기가 짝수인 경우를 생각해 보자.

1. 양수 수열 ex) {1, 2, 3, 4, 5, 6}
   두 개씩 묶되, 묶이는 두 수의 합이 곱보다 큰 경우(1과 2처럼) 합을 더하도록 한다.

2. 음수 수열 ex) {-1, -2, -3, -4, -5, -6}
   두 개씩 묶어서 곱한 값을 더한다.

3. 섞이는 경우
   ex) {3, 2, 1, -1, -2, -3}, {5, -1, -2, -3, -4, -5}, {5, 4, 3, 2, 1, -5} 등
   양수 케이스처럼 두 개씩 묶되, 묶이는 두 수의 합이 곱이 크면 합을 더함(1과 -1처럼)

다음으로, 수열의 크기가 홀수인 경우를 생각해 보자.

1. 양수 수열 ex) {5, 4, 3, 2, 1}
   앞에서부터 두 개씩 묶은 후 남은 하나(1)를 더한다

2. 음수 수열 ex) {-1, -2, -3, -4, -5}
   뒤에서부터 두 개씩 묶은 후 남은 하나(-1)를 더한다.

3. 섞인 수열 ex) {4, 3, 2, 1, -1, -2, -3}
   처음으로 0 이하가 나오는 인덱스를 구한다.
   0부터 해당 인덱스까진 앞에서부터 묶고, 해당 인덱스부터 끝까지는 뒤에서부터 묶는다.
   묶을 때 양수 부분 또는 음수 부분의 개수를 생각해, 홀수 개라면 마지막 남은 수는 더한다.

위의 예를 보면, {4, 3, 2, 1, -1, -2, -3}에서 처음 0 이하가 나오는 인덱스는 4이다.
0~3까지는 (4, 3), (2, 1) 두개를 묶는데, 앞에서 말했듯 (2, 1)은 더한 값으로 처리한다.
그리고 4~6까지는 뒤에서부터 (-2, -3)을 묶고, 음수 개수가 홀수 개이므로 -1을 더한다.
그래서 12 + 3 - 1 + 6 = 20을 구한다.

+) 0을 포함해 처음으로 0 이하가 나오는 인덱스를 구하는 이유
{4, 3, 2, 1, 0, -1, -2}
{3, 2, 1, 0, -1, -2, -3}
이런 케이스들이 있다.

{4, 3, 2, 1, 0, -1, -2}같이 양쪽에 양수와 음수가 짝수 개가 있는 케이스라면 괜찮다.

하지만 {3, 2, 1, 0, -1, -2, -3}같이 양쪽에 양수와 음수가 홀수 개가 있는 케이스라면, 0을 음수 부분에 포함시키는 것이 맞다.

왜냐하면 (3, 2)와 (-2, -3)을 묶고 {1, 0, -1}이 남는다고 생각해보자.

값이 최대가 되기 위해선 0과 -1을 묶어 0으로 만들고 1을 더해야 한다.

그것은 곧 수열을 {3, 2, 1}과 {0, -1, -2, -3}으로 나누는 것과 같다.
즉 0을 음수 부분으로 보내야 한다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val sorted = IntArray(N){readLine().toInt()}.sortedArrayDescending()

    var ans = 0
    if(sorted.size % 2 == 0){
        ans = getPartialSum(sorted, 0, sorted.size)
    }else{
        val m = getFirstMinus(sorted)
        val left = getPartialSum(sorted, 0, m)
        val right = getPartialSumRev(sorted, m, sorted.size)

        ans = left + right
    }

    print(ans)
}

fun getPartialSumRev(arr: IntArray, start: Int, end: Int): Int{
    var sum = 0
    for(i in end - 1 downTo start + 1 step 2){
        val s = arr[i] + arr[i - 1]
        val m = arr[i] * arr[i - 1]

        sum += if(s > m) s else m
    }

    if((end - start) % 2 == 1) sum += arr[start]
    return sum
}

fun getPartialSum(arr: IntArray, start: Int, end: Int): Int{
    var sum = 0
    for(i in start until end - 1 step 2){
        val s = arr[i] + arr[i + 1]
        val m = arr[i] * arr[i + 1]

        sum += if(s > m) s else m
    }

    if((end - start) % 2 == 1) sum += arr[end - 1]
    return sum
}

fun getFirstMinus(arr: IntArray): Int{
    var idx = arr.size - 1
    for(i in arr.indices){
        if(arr[i] <= 0){
            idx = i
            break
        }
    }
    return idx
}