문제 설명
길이가 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이 되어 최대가 된다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/1744
제한 사항
풀이
문제를 요약하면 주어진 수들의 합을 최대로 만드는 것이다.
이때 임의의 두 수를 한 번씩만 곱해서 더할 수도 있다.
합을 최대로 만들어야 하므로 큰 수는 큰 수끼리 곱하는 것이 이득이다.
음수끼리의 곱도 해당된다.
따라서 음수와 양수를 구분하여 저장한 후 정렬을 통해 절댓값이 큰 수부터 곱하며 합을 구해 나가면 된다.
-1 2 1 34개의 입력이 주어졌다고 가정해 보자.
이를 음수와 양수로 나누면 {-1}, {1, 2, 3}으로 나눌 수 있다.
이때 큰 수부터 차례로 곱해서 더하면 $2*3$을 더할 수 있고 남은 수들은 곱할 것이 없어 그대로 더하게 된다.
$2*3 + 1 + (-1) = 6$이 된다.
기본적인 구조는 이렇게 진행되지만 몇 가지 예외가 존재한다.
바로 1과 0에 대해 처리해줘야 한다.
우선 1은 양수이지만 곱해도 이득이 없다.
따라서 1은 곱하는 것보다 바로 더해주는 것이 합을 최대로 만드는 전략이 된다.
if (num == 1) ans += num;
else positive.push_back(num);
그리고 0에 대해 처리해야 한다.
0은 사실 양수도 아니고 음수도 아니다.
하지만 합을 최대로 만들기 위해서는 0을 음수 쪽에 포함해야 한다.
음수와 0을 곱해 0으로 만들게 되면 음수를 더하지 않을 수 있기 때문이다.
if (num <= 0)
{
negative.push_back(num);
}
마지막으로 정렬 기준에 대해서만 유의하면 된다.
양수의 경우 당연히 큰 수부터 곱해 나간 뒤 남은 요소는 더해주는 방법이 최대를 만드는 전략이 된다.
음수의 경우 절댓값이 큰 수(더 작은 수)끼리 곱해야 최댓값을 만드는 전략이 된다.
따라서 다음과 같이 정렬해 주어야 한다.
sort(negative.begin(), negative.end(), greater<int>());
sort(positive.begin(), positive.end());
이제 음수, 양수에서 각각 2개씩 뽑아 곱해서 더하면 된다.
while (negative.size() > 1)
{
int a = negative.back();
negative.pop_back();
int b = negative.back();
negative.pop_back();
ans += a * b;
}
while (!negative.empty())
{
ans += negative.back();
negative.pop_back();
}
전체 코드
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321
using namespace std;
int N;
vector<int> positive, negative;
int main()
{
INPUT_OPTIMIZE;
cin >> N;
int ans = 0;
for (int i = 0; i < N; i++)
{
int num;
cin >> num;
if (num <= 0)
{
negative.push_back(num);
}
else
{
if (num == 1) ans += num;
else positive.push_back(num);
}
}
sort(negative.begin(), negative.end(), greater<int>());
sort(positive.begin(), positive.end());
while (negative.size() > 1)
{
int a = negative.back();
negative.pop_back();
int b = negative.back();
negative.pop_back();
ans += a * b;
}
while (!negative.empty())
{
ans += negative.back();
negative.pop_back();
}
while (positive.size() > 1)
{
int a = positive.back();
positive.pop_back();
int b = positive.back();
positive.pop_back();
ans += a * b;
}
while (!positive.empty())
{
ans += positive.back();
positive.pop_back();
}
cout << ans;
return 0;
}