BOJ 1744 - 수 묶기

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

주어진 수열의 합을 구하는데 숫자를 두개씩 묶을 수 있다.

두개씩 묶인 수는 곱할 수 있다. 한 번 묶인 수는 다른수와 묶일수 없다.

이때 수열의 합 중 최대값을 구하시오.

Solution

(1) 양수는 양수끼리 곱해준다. 단 가능한 큰 수 끼리 곱해준다.

(2) 음수는 음수끼리 곱해준다. 단 가능한 작은 수 끼리 곱해준다.

ex> -3 x - 4 > -2 x -1

(3) 1은 묶지 않는것이 좋다. 곱해도 아무런 의미가 없기때문.

1, 4, 2, 3 이 들어왔을때 (4x3) + 2 + 1 이 베스트이지 (4x3) + (2x1) 은 더할수 있는 1을 무의미하게 날리는 꼴밖에 되지 않는다.

(4) 0은 음수를 없앨때 사용할 수 있다.

-4, -3, -1, 0 이 들어왔을때 (-4x-3) + (-1) + 0 < (-4x-3) + (-1x0) 이기 때문.

이 조건을 충족하기 위해서는 음수의 개수가 홀수개여야 한다.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //양수는 양수끼리 곱함, 큰수끼리 곱해줌
    //음수는 음수끼리 곱함, 작은수끼리 곱해줌
    //음수중에 한개만 남았을시에는 0과 곱함. ( 모든 음수 < 0 )
    //1은 묶지않는것이 베스트다. (의미없는 곰셈을 하게됨)

    vector<int> postive;
    vector<int> negative;
    int one = 0, zero = 0;

    int t; cin >> t;

    while (t--) {
        int temp; cin >> temp;
        if (temp == 1)
            one++;
        else if (temp > 0)
            postive.push_back(temp);
        else if (temp < 0)
            negative.push_back(temp);
        else
            zero++;
    }

    int ans = one; //애초에 묶지 않을 1

    if (postive.size() % 2)
        postive.push_back(1); //2개씩 묶는 과정을 일반화하기위함 
    if (negative.size() % 2)
        negative.push_back(zero ? 0 : 1); //0의 여유분이 존재하면 넣어줌

    sort(postive.begin(), postive.end());
    reverse(postive.begin(), postive.end()); //내림차순을 위한 리버스

    sort(negative.begin(), negative.end());

    for (int i = 0; i < postive.size(); i += 2) {
        ans += postive[i] * postive[i + 1];
    }

    for (int i = 0; i < negative.size(); i += 2) {
        ans += negative[i] * negative[i + 1];
    }

    cout << ans << '\n';

    return 0;
}

if (postive.size() % 2)
postive.push_back(1);

2개씩 묶어서 합하는 과정을 일반화하기위해 양수의 개수가 홀수개일때면 1을 넣어서 반복문에 문제가 없게 만들었다. 1은 곱할때 아무 의미가 없기때문.

참고 : https://code.plus/course/43 , 그리디 알고리즘(연습)