백준 14753) MultiMax (브루트포스 알고리즘, 정렬, case work)

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

14753번: MultiMax

 

문제

There are n cards, each with an integer on it where two or more cards can have the same integer. From these cards, we want to select two or three cards such that the product of numbers on the selected cards is maximum. For example, assume that there are 6 cards with numbers: 5, 10, -2, 3, 5, and 2. If we select three cards with numbers, 5, 10, and 5, then the product of the three numbers is 250, which is the maximum product. Let us consider another example of four cards with numbers: 10, 0, -5, 2. In this example, if we select two cards with numbers, 10 and 2, then the product of these two numbers is 20, which is the maximum product.

Given n numbers on cards, write a program to compute the maximum product of numbers on two or three cards.

입력

Your program is to read from standard input. The input starts with a line containing an integer, n (3 ≤ n ≤ 10,000), where n is the number of cards. In the following line, n numbers on the cards are given. These numbers are integers between -1,000 and 1,000 inclusively.

출력

Your program is to write to standard output. Print exactly one line which contains the maximum product.

 

예제 입력 1

6
5 10 -2 3 5 2

예제 출력 1

250

예제 입력 2

4
10 0 -5 2

예제 출력 2

20

 

---

 

영어가 다소 길어서 처음에 문제를 접하고 당황했지만 요약하면 다음과 같다.

n개의 카드 중에 2개 또는 3개를 선택해서 곱한 값이 최대가 되는 값을 찾는 것이다.

 

2개 또는 3개를 찾아야 하므로 브루트포스 알고리즘이라고 생각할테고,

최대 3개의 반복문을 돌려야 하니 O(n^3) 까지 시간복잡도가 나올 수 있다.

그리고 정렬을 수행하게 된다면 최대 O(n^4)를 고려해야 한다.

 

 

하지만 문제에서 최대 100000개를 입력받는다면 100000^3의 값은 최소 십억이 넘는다.

이는 브루트포스 알고리즘으로 접근하기에는 시간초과가 날 것이 분명하다.

 

 

그래서 제목에 쓴 case work 가 이 문제를 해결할 수 있는 방법이 된다.

말 그대로 case를 나눠서 작업을 실시하는 용어인 것 같다.

 

 

 

이를 적용한 전체 코드는 다음과 같다.

(설명 추가)

 

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = readLine().split(" ").map { it.toInt() }.toIntArray()
    val size = arr.size
    //정렬을 수행하는 이유는
    //가장자리의 값들을 곱하는 것이 최대가 되기 때문이다.
    arr.sort()

    //카드를 3개 선택할 때
    
    //case1 : 맨 처음 3개
    val case1 = arr[0] * arr[1] * arr[2]
    
    //case2 : 맨 끝 3개
    val case2 = arr[size-3] * arr[size-2] * arr[size-1]
    
    //case3 : 맨 처음 1개, 맨 끝 2개
    val case3 = arr[0] * arr[size-2] * arr[size-1]
    
    //case4 : 맨 처음 2개, 맨 끝 1개
    val case4 = arr[0] * arr[1] * arr[size-1]
    
    
    //카드를 2개 선택할 때
   
    //case5 : 맨 처음 2개
    val case5 = arr[0] * arr[1]
    
    //case6 : 맨 처음 1개, 맨 끝 1개
    val case6 = arr[0] * arr[size-1]
    
    //case7 : 맨 끝 2개
    val case7 = arr[size-2] * arr[size-1]


    //maxOf는 최대 3개까지 비교 가능
    val result1 = maxOf(case1,case2,case3)
    val result2 = maxOf(case4,case5,case6)
    println(maxOf(result1,result2,case7))
}