Codeforces #1406B Maximum Product

문제

https://codeforces.com/problemset/problem/1406/B

걸린 시간

01 : 16 : 18 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

vector<int> pos, neg;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, a;
        cin >> n;
        pos.clear(); neg.clear(); 
        for(int i = 0; i < n; i++){
            cin >> a;
            if(a >= 0)
                pos.push_back(a);
            else
                neg.push_back(a);
        }
        sort(pos.begin(), pos.end(), greater<int>());
        sort(neg.begin(), neg.end());
        long long ans = -pow(3000, 5), cur = 1;
        // 입력이 음수로만 주어질 때
        if(pos.size() == 0){
            for(int j = 0; j < 5; j++)
                cur *= neg[neg.size()-j-1];
            ans = cur;
        }
        // 최대 양수, 음수 조합
        for(int i = 0; i <= 5; i++){
            cur = 1;
            if(5-i > pos.size() || i > neg.size()) continue;
            for(int j = 0; j < 5-i; j++)
                cur *= pos[j];
            for(int j = 0; j < i; j++)
                cur *= neg[j];
            ans = max(ans, cur);    
        }
        cout << ans << "\n";
    }
    return 0;
}

원소 5개로 이루어진 부분배열의 최대곱을 구하는 문제이다.

풀이 방법은 여러가지가 있는 것 같은데 그 중에서 정렬 후 최대곱이 나올 수 있는 경우의 수를 모두 시도해보는것이 제일 간단해보였다.

최대곱은 양수 음수의 개수가 각각 (5, 0), (3, 2), (1, 4) 인 3가지 경우에서 발생할 것이라 생각하고 풀이했지만 틀린 답이 출력되었다.

입력이 모두 음수로 주어질 때가 반례였다.

1
5
-5 -4 -3 -2 -1 -1
정답 : -12
출력 : -60

음수의 경우 절대값이 작은 5개의 수들의 곱이 최대값이다.

다른 풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

vector<int> a;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        a.resize(n);
        for(int& i : a) cin >> i;
        sort(a.begin(), a.end());
        long long ans = -pow(3000, 5);
        for(int i = 0; i <= 5; i++){
            long long cur = 1;
            for(int j = 0; j < 5-i; j++)
                cur *= a[j];
            for(int j = 0; j < i; j++)
                cur *= a[n-1-j];
            ans = max(ans, cur);    
        }
        cout << ans << "\n";
    }
    return 0;
}

하나의 배열만을 사용하면 문제가 더욱 간단해진다.

정렬 후 앞과 뒤에서 적절히 5개를 선택하게 되므로 값이 최대가 되는 경우의 수를 빠짐없이 시도해볼 수 있다.