백준 1744 - 수 묶기

 

 

문제 설명

길이가 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 3

 4개의 입력이 주어졌다고 가정해 보자.

이를 음수와 양수로 나누면 {-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;
}

---