백준 1744 - 수 묶기

문제링크

• 백준 1744

문제설명

• 길이가 N인 수열이 주어질 때, 그 수열의 합을 구하려고 한다.
• 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶을 수 있다.
• 두 수는 위치에 상관없이 묶을 수 있지만, 자기 자신과 묶는 것은 불가능하고 딱 한번만 묶을 수 있다.
• 어떤 수를 묶게 되면 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
• 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2x3)+(4x5) = 27이 되어 최대가 된다.
• 수열이 주어졌을 때, 수열의 각 수를 적절히 묶어 그 합이 최대가 되게 하라.

문제접근

• 양수의 경우 가장 큰 두 수끼리 묶는 것이 합을 최대로 만드는 방법이다.
  • 단, 1의 경우 어떤 수와 묶는 것보다 그대로 유지하는 것이 최대 합을 구할 수 있는 방법이므로 1의 개수는 따로 체크하고, 마지막에 따로 더해준다.
• 음수의 경우도 절댓값이 가장 큰 두 수끼리 묶는 것이 합을 최대로 만드는 방법이다.
  • 음수의 개수가 홀수이면서 0 이 존재한다면, 절댓값이 가장 작은 음수와 0을 묶어 음수를 모두 없앨 수 있다.
  • 양수와는 달리 모든 음수는 묶는 것이 합을 최대로 만드는 방법이다. 따라서, 가능한 모든 음수는 묶어준다.

구현

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> negativeArr, positiveArr;
	bool zero = false;
	int cntOne = 0;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		if (num > 1) positiveArr.push_back(num);
		else if (num < 0)
		{
			num = abs(num);
			negativeArr.push_back(num);
		}
		else if (num == 1) cntOne++;
		else if (num == 0) zero = true; // 0은 음수가 홀수개인 경우 묶이지 않은 절댓값이 가장 작은 음수와 곱해진다.
	}

	// 내림차순 정렬
	sort(positiveArr.begin(), positiveArr.end(), greater<int>());
	sort(negativeArr.begin(), negativeArr.end(), greater<int>());

	vector<int> newArr;
	if (positiveArr.size() > 0)
	{
		// 홀수인 경우 제일 뒤에 있는 수는 먼저 새로운 순열에 넣어두고 짝수로 만든다.
		if (positiveArr.size() % 2 == 1)
		{
			newArr.push_back(positiveArr.back());
			positiveArr.pop_back();
		}
		for (int i = 0; i < (int)positiveArr.size() - 1; i += 2) // 형변환 필수
		{

			newArr.push_back(positiveArr[i] * positiveArr[i + 1]);
		}
	}

	if (negativeArr.size() > 0)
	{
		if (negativeArr.size() % 2 == 1)
		{
			if (zero == false)
			{
				newArr.push_back(negativeArr.back() * (-1));
			}
			// 0이 있는 경우 0과 음수를 묶어서 0으로 만들어줌. 새로운 수열에는 안들어감
			negativeArr.pop_back();
		}
		for (int i = 0; i < (int)negativeArr.size() - 1; i += 2) // // 형변환 필수
		{
			newArr.push_back(negativeArr[i] * negativeArr[i + 1]);
		}
	}
	long long ans = 0;
	for (auto ele : newArr)
	{
		ans += (long long)ele;
	}
	ans += cntOne;
	cout << ans << "\n";
}

• 벡터 컨테이너를 다룰 때 반복문 조건에 size() 함수를 호출해서 사용해왔는데, size() 함수는 반환 자료형 타입이 size_t 이다.
• 그동안 size() - 1 처럼 size_t 자료형과 상수 값을 빼는 연산을 할 때 타입에 전혀 신경쓰지 않고 있었는데, size() 값이 0인 경우 해당 반복문 조건이 true 가 되면서 무한 루프에 빠지는 현상을 발견했다.
  • size_t 는 unsigned_int 자료형이기 때문에 -1 값이 할당되면 MSB 가 1로 설정되어 음수가 아니라 unsinged_int 범위에 해당하는 엄청 큰 양수가 된다.(무한루프라고 느꼈던 이유)
  • 암묵적 형변환의 위험성 중 하나… 이번 문제 풀이를 통해 느낀 것이 천만다행이다!
• 명시적으로 형변환을 해주고 나니 해당 문제가 해결되었다. 명시적 형변환을 습관화하자!