[알고리즘] C++ 백준 1744 수 묶기

 

백준 1744

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

풀이 전 나의 생각

문제를 처음 봤을 때 그냥 최대값들만 곱해서 더하면 될 것이라고 생각했는데 자세히보니 아니다.

조건을 보면 -1000 ~ 1000의 크기를 가지는 수열이기 때문에 실버 문제보다는 조금 더 생각해야 할 필요가 있다.

음수, 0, 1, 양수 이 4가지를 가지고 조건을 만들어보면

 

1. 양수 * 양수 

 

2. 음수 * 음수 

 

3. 1이 나왔을 때

 

4. 0이 나왔을 때

 

이렇게 4가지가 나온다.

 

여기서 중요한건 1과 0을 어떻게 처리하느냐에 따라 달렸다.

1은 음수든 양수든 곱하면 무조건 손해를 본다. 그래서 1은 최종 결과값에 더해주는 것으로 처리한다.

0은 이득을 보는 조건이 음수 * 음수를 해서 남은 음수에 0을 곱해주는 것 뿐이다.

 

그럼 0과 1은 수열의 값을 받을 때 미리 처리해 놓으면 되고

나머지 음수, 양수는 조건에 맞게 최대값들로 곱해주어 최종값에 더해주면된다.

양수의 배열 크기가 홀수라면 최종값에 나머지 하나의 값을 추가해주고

음수의 배열 크기가 홀수라면 0이 있는지 확인 후 나머지 음수값을 그대로 추가할지 안할지 조건을 걸어주면 된다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	vector<int>pn;
	vector<int>nn;

	int n = 0;
	int res = 0;
	int zCnt = 0;
	cin >> n;

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

		if (num == 0)
		{
			zCnt++;
		}
		else if (num == 1)
		{
			res += 1;
		}
		else if (num > 1)
		{
			pn.push_back(num);
		}
		else
		{
			nn.push_back(num);
		}
	}

	if (pn.size() >= 1)
	{		
		sort(pn.begin(), pn.end(), greater<int>());
		int ptmp = 0;
		for (int i = 0; i < pn.size(); i++)
		{
			ptmp = pn[i];
			if (i % 2 == 1)
			{
				res += pn[i - 1] * pn[i];
				ptmp = 0;
			}
		}
		res += ptmp;
	}

	if (nn.size() >= 1)
	{
		sort(nn.begin(), nn.end());
		int ntmp = 0;
		for (int i = 0; i < nn.size(); i++)
		{
			ntmp = nn[i];
			if (i % 2 == 1)
			{
				res += nn[i - 1] * nn[i];
				ntmp = 0;
			}
		}

		if (zCnt == 0)
		{
			res += ntmp;
		}
	}

	cout << res;
}