백준 14753 C++

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.

---

카드가 n 개 있고, 각각의 카드는 정수이며, 카드는 중복 가능하다.

이 카드 중에서 2개 혹은 3개의 카드를 뽑아서 선택된 카드의 곱이 최대가 되어야 한다.

n개의 카드가 주어졌을떄 2개 혹은 3개의 카드의 최대 곱을 구하여라.

---

입력

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.

카드는 -1000부터 1000까지 숫자고 10000개의 카드가 주어진다.

---

출력

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

---

처음에 완전탐색으로 시도해봤는데 시간초과가 떴다.

정렬을 사용하면 풀 수 있다.

 

카드를 내림차순으로 정렬한 후 n번 루프를 2번 도는데, 첫번째 n번 도는 루프는 카드가 2개일 때 곱의 최대이고,

두번쨰 n번 도는 루프는 카드가 3개일떄 곱의 최대이다.

이떄, 내림차순 정렬 시, 첫번쨰 카드가 양수이고 , 맨뒤와 맨뒤 -1 카드가 음수일때, 카드의 곱이 최대가 될 수 있다.

 

(내림차순 정렬하면 음수가 가장 작은 게 뒤에 오기 떄문에)->이 경우를 뺴먹어서 애를 먹었다..ㅏ

---

 전체 소스 코드->

#include <iostream>

#include <algorithm>

using namespace std;

int max(int a,int b){

    if(a>b){

        return a;

    }

    else{

        return b;

    }

}

int main(void){

    int n;

    cin >> n;

    int arr[10000];

    for(int i = 0;i<n;i++){

        cin >> arr[i];

    }

   

    sort(arr,arr+n,greater<int>()); //내림차순 정렬

    int max_product = -200000000; //곱의 최대 초기화

    for(int i = 0;i<n;i++){ //카드개수 2개일떄

        if(i>=1){

            max_product =max(max_product,arr[i]*arr[i-1]);

        }

    }

   

    for(int i = 0;i<n;i++){ //카드개수 3개일떄

        if(i>=2){

            max_product = max(max_product,arr[i]*arr[i-1]*arr[i-2]);

        }

    }

   

    max_product = max(max_product,arr[0]*arr[n-1]*arr[n-2]);

//맨 처음이 양수고 맨뒤와 맨뒤-1가 음수일떄 곱이 가장 커질 수 있음.

    cout << max_product;

}