[C/C++] BOJ(백준) 1744 "수 묶기" 문제 풀이 & 소스 코드

#문제정보

출처 : www.acmicpc.net/problem/1744

난이도 : 골드4

분류 : 그리디(GREEDY) 알고리즘

 

#문제분석

입력받은 수들을 양수,음수,0 으로 각각 다른 벡터에 저장해서 풀이했습니다.

vector<int> pos; // 양수 벡터
vector<int> neg; // 음수 벡터
vector<int> zero; // 0 저장 벡터
vector<int> res; // 출력 값 

 

 

CASE1 : 양수벡터

양수가 홀수개인 경우 : 가장 작은 값을 결과값에 더합니다.

양수가 짝수개인 경우 : 양수벡터를 오름차 정렬한 후 , 뒤에서 부터 2개씩 묶어 곱한 뒤 결과값에 더합니다.

(내림차 정렬한 후 앞에서 부터 2개씩 곱해도 상관은 없습니다.)

// positive 
	int pSize = pos.size();
	if (pSize % 2 != 0)
	{
		res.push_back(pos[0]);
	}
	
	for (int i = pSize - 1 ; i > 0 ; i-=2)
	{
		res.push_back(pos[i] * pos[i - 1]);
	}

 

CASE2 : 음수벡터

음수가 홀수개 & 0이 포함된 경우 : 가장 큰값 |절댓값이 가장 작은값| 과 0을 곱합니다.

음수가 홀수개 & 0이 포함되지 않은 경우 : 가장 큰값 |절댓값이 가장 작은값|을 결과값에 더합니다.

음수가 짝수개인 경우 : 음수벡터를 오름차 정렬한 후 , 앞에서 부터 2개씩 묶어 곱한 뒤 결과값에 더합니다.

// negative
	int nSize = neg.size();
	if (nSize % 2 != 0)
	{
		if (zero.size() > 0)
		{
			zero.pop_back();
		}
		
		else
		{
			res.push_back(neg[nSize - 1]);
		}
	}
	
	for (int i = 0 ; i < nSize - 1 ; i+=2)
	{
		res.push_back(neg[i] * neg[i+1]);
	}

 

#소스코드

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

vector<int> pos; // 양수 벡터
vector<int> neg; // 음수 벡터
vector<int> zero; // 0 저장 벡터
vector<int> res; // 출력 값 

int main()
{
	int n;
	cin >> n;
	int tmp;
	for (int i = 0 ; i < n ; i++)
	{
		cin >> tmp;
		if (tmp > 0)
		{
			if (tmp == 1){
				res.push_back(tmp);
			}
			else{
				pos.push_back(tmp);
			}
		}
		
		else if (tmp < 0)
		{
			neg.push_back(tmp);
		}
		
		else
		{
			zero.push_back(tmp);
		}
	} 
	
	sort(pos.begin(), pos.end());
	sort(neg.begin(), neg.end());
	
	// positive 
	int pSize = pos.size();
	if (pSize % 2 != 0)
	{
		res.push_back(pos[0]);
	}
	
	for (int i = pSize - 1 ; i > 0 ; i-=2)
	{
		res.push_back(pos[i] * pos[i - 1]);
	}
	
	// negative
	int nSize = neg.size();
	if (nSize % 2 != 0)
	{
		if (zero.size() > 0)
		{
			zero.pop_back();
		}
		
		else
		{
			res.push_back(neg[nSize - 1]);
		}
	}
	
	for (int i = 0 ; i < nSize - 1 ; i+=2)
	{
		res.push_back(neg[i] * neg[i+1]);
	}
	
	int sum = 0;
	for (int i = 0 ; i < res.size(); i++)
	{
		sum += res[i];
	}
	
	cout << sum;
	
	return 0; 
}