백준) 1744 수 묶기

1744. 수 묶기

문제

길이가 N인 수열이 주어졋을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 어떤 인접한 원소끼리를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때, 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

수를 적절히 묶어 그 합이 최대값을 출력한다. 정답은 항상 231보다 작다.

예제 입력 

4
-1
2
1
3

예제 출력 

6

1. 접근

그리디 알고리즘. 여러 수들을 묶거나 더해서 가장 큰 수를 만들려면 가장 큰 두 수(양수) 나 가장 작은 수 (음수)들을 묶어야 한다.

2. 풀이

0 < a < b < c < d 인 수 네 개를 규칙에 따라 가장 큰 합을 만들려면 어떻게 해야 할까?

1) a * b + c * d

2) a * c + b * d

3) a * d + b * c

직관적으로 1번이 가장 큰걸 알고 있다.

1번과 2번을 빼면 a * (b - c) > d * (b - c) 이므로 1번이 더 크다.

1번과 3번을 빼면 a * (b - d) > c * (b - d) 이므로 1번이 더 크다. 

음수에 양수를 곱해봤자 전체 합은 작아만지므로 음수는 가능한 음수와만 곱해야함이 자명하다.

따라서 음수와 양수를 따로 생각해서 가장 큰 수 두 개씩 묶어나가면 되겠다.

다만 1과 0은 예외적인 수인데, 0은 음수를 묶어나가고 남은 짜투리에 곱해서 0으로 만드는데 사용하고,

1은 곱해봤자 총 합을 늘리는데 도움이 되지 않으므로 1은 더하는데만 사용하면 되겠다.

3. 코드

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
 
int n, i, tmp, z, one, as, bs, sum;
priority_queue<int, vector<int>, greater<int>> a;
priority_queue<int, vector<int>, less<int>> b;
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &tmp);
        if (tmp == 1)
            one++;
        else if(tmp > 0)
            a.push(tmp);
        else if (tmp < 0)
            b.push(tmp);
        else
            z++;
    }
    if (a.size() % 2 == 1)
        a.push(1);
    if (b.size() % 2 == 1)
        z == 0 ? b.push(1) : b.push(0);
 
    as = a.size() / 2;
    bs = b.size() / 2;
    for (i = 0; i < as; ++i) {
        tmp = a.top();
        a.pop();
        sum += a.top()*tmp;
        a.pop();
    }
    for (i = 0; i < bs; ++i) {
        tmp = b.top();
        b.pop();
        sum += b.top()*tmp;
        b.pop();
    }
    printf("%d", sum + one);
    return 0;
}

양수들의 큐와 음수들의 큐를 처리한 나머지 짜투리를 예외처리하기 귀찮으므로 추가로 1이나 0을 넣어주는 센스