[알고리즘] 수 묶기 (백준 1744번)

1744번: 수 묶기

 그리디하게 풀 수 있는 문제이다. 수를 정렬했을 때 양수 기준으로 가장 큰 수부터 곱해나간다. 단, 1과 쌍이 지어지는 경우는 그냥 더하는게 더 수가 크기 때문에 항상 list[i] * list[i+1]와 list[i] + list[i+1] 중 어떤게 더 큰지 비교해가면서 더한다.

 음수는 반대로 가장 작은 수부터 곱해야지 가장 큰 값이 나온다. EX) (-5 * -1 = 5) > (-4 * -1 = 4)

 

Solution

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

import kotlin.collections.HashMap
import kotlin.math.max

import kotlin.math.min

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))


fun solution() {

    var N = br.readLine().toInt()

    var list = IntArray(N, {br.readLine().toInt()})

    list.sortDescending()

    var result = 0

	//양수 계산
    var i = 0

    while(i < N && list[i] > 0)
    {
        if(i == N - 1)
        {
            result += list[i]
            i++
        }
        else
        {
            if(list[i] * list[i + 1] > list[i] + list[i + 1])
            {
                result += list[i] * list[i + 1]
                i += 2
            }
            else
            {
                result += list[i]
                i++
            }
        }
    }

	//음수 계산
    i = N - 1

    while(i >= 0 && list[i] < 0)
    {
        if(i == 0)
        {
            result += list[i]
            i--
        }
        else
        {
            if(list[i] * list[i - 1] > list[i] + list[i - 1])
            {
                result += list[i] * list[i - 1]
                i -= 2
            }
            else
            {
                result += list[i]
                i--
            }
        }

    }
    bw.write(result.toString())
}



fun main() {
    solution()


    br.close()
    bw.close()
}