1744번: 수 묶기

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

1744번: 수 묶기

언어 : Kotlin

 

문제 설명 :

길이가 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보다 작다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
4 -1 2 1 3	6
6 0 1 2 4 3 5	27
1 -1	-1
3 -1 0 1	1
2 1 1	2

 

다른 사람의 풀이 : 

https://best-human-developer.tistory.com/8

(Kotlin) 백준 1744 - 수 묶기

 

위 풀이를 보면, Greedy 방식으로 풀었다.

1) n을 입력 받고, 수를 입력 받을 때 양수와 음수를 따로 저장하며, 0이 있다면 체크, 1이 있다면 바로 result값에 더해준다.

2) 이후 양수와 음수 리스트를 정렬시킨다.

(양수는 내림차순, 음수는 오름차순 // 가장 큰 수를 위해 양수는 큰 수 끼리 곱하기, 음수는 절대값이 큰 수 끼리 곱하기)

 

3) 양수 리스트는 개수가 0개 라면 0, 1개 라면 그 원소를 result에 더한다.

짝수개라면 크기 순으로 2개씩 묶어 곱한 것을 합해 result에 더한다.

홀수개라면 크기 순으로 가장 작은 수와 나머지 짝수 개를 묶은 것을 합하여 result에 더한다.

 

4) 음수 리스트는 양수 리스트와 절대값에 대해 같은 방식으로 처리한다.

5) 음수 리스트에 홀수개 && 0이 수열에 존재한다면, 더해줬던 가장 큰 음수를 result에서 뺀다.

 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    
    // 1)
    val n = readLine().toInt()
    var result = 0
    val negative = mutableListOf<Int>()
    val positive = mutableListOf<Int>()
    var zero = false
    repeat(n) {
        val num = readLine().toInt()
        when {
            num == 0 -> zero = true
            num == 1 -> result++
            num > 1 -> positive += num
            else -> negative += num
        }
    }
    
    // 2)
    positive.sort()
    negative.sortDescending()
    
    // 3)
    result += sequence(positive, positive.size) + sequence(negative, negative.size)
    
    // 4, 5)
    bw.write("${if (negative.size % 2 != 0 && zero) result - negative[0] else result}")
    bw.flush()
    bw.close()
}

fun sequence(sequence: MutableList<Int>, size: Int): Int {
    return when {
        size == 0 -> 0
        size == 1 -> sequence[0]
        size % 2 == 0 -> sequence.chunked(2).map { it[0] * it[1] }.reduce { acc, i -> acc + i }
        else -> sequence[0] + sequence.subList(1, size).chunked(2).map { it[0] * it[1] }.reduce { acc, i -> acc + i }
    }
}