백준 1744 수 묶기 | C++

 

 

이번 포스팅은 백준 1744번 수 묶기입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/1744

1744번: 수 묶기

 

 

 

기본 알고리즘

vector sort()

 

 

풀이

2개씩 묶어 곱한 합의 최댓값 구하기

 

곱셈의 값이 커지려면

▷양수, 음수는 서로 곱한다

▷ 1은 곱하는 것이 무의미함 = 개별로 더하는 것이 합의 최댓값 유도

▷0은 더하는 것이 무의미함 = 0은 음수의 개수가 홀수일 때 절댓값이 가장 작은 음수와 곱하는 것이 합의 최댓값 유도

 

→ 입력 받을 때 양수, 음수, 0을 각각 다른 벡터에 저장

→ 1은 원소의 총합을 구할 벡터(ans)에 저장

 

sort() 함수로 양수, 음수 벡터를 오름차순으로 정렬

 

양수 벡터

원소의 개수가 홀수이면 가장 작은 값을 ans에 저장

뒤에서부터 2개씩 묶어 곱한 값을 ans에 저장

 

음수 벡터

원소의 개수가 홀수이고 0 포함

    가장 큰 값(절댓값이 가장 작음)을 0과 곱함

원소의 개수가 홀수이고 0 없음

    가장 큰 값(절댓값이 가장 작음)을 ans에 저장

앞에서부터 2개씩 묶어 곱한 값을 ans에 저장

 

예시)

입력

9

-4 1 -3 1 -1 0 5 1 2

 

양수, 음수, 1, 0 구분 후 정렬

-4 -3 -1

0

1 1 1

2 5

 

합의 최댓값

(-4*-3) + (-1*0) + 1 + 1 + 1 + (2*5)

 

 

 

전체 코드

//백준1744 수묶기                                                            
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int N;
    cin >> N;
 
    vector<int> pos; //양수 저장
    vector<int> neg; //음수 저장
    vector<int> zero; //0 저장
    vector<int> ans; //출력 = ans벡터의 원소의 총합
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        if (num > 0) {
            if (num == 1) {
                ans.push_back(num);
            }
            else {
                pos.push_back(num);
            }
        }
        else if (num < 0) {
            neg.push_back(num);
        }
        else { //num==0
            zero.push_back(num);
        }
    }
 
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
 
    /*양수*/
    int pSize = pos.size();
    if (pSize % 2 != 0) {
        ans.push_back(pos[0]);
    }
    for (int i = pSize - 1; i > 0; i-=2) {
        int big = pos[i];
        int small = pos[i - 1];
        int mul = big * small;
        ans.push_back(mul);
    }
 
    /*음수*/
    int nSize = neg.size();
    if (nSize % 2 != 0) {
        if (zero.size() > 0) {
            zero.pop_back();
        }
        else {
            ans.push_back(neg[nSize - 1]);
        }
    }
    for (int i = 0; i < nSize-1; i += 2) {
        int small = neg[i];
        int big = neg[i + 1];
        int mul = small * big;
        ans.push_back(mul);
    }
 
    /*출력 = ans벡터의 원소의 총합*/
    int sum = 0;
    for (int i = 0; i < ans.size(); i++) {
        sum += ans[i];
    }
    cout << sum;
    
 
    return 0;
}