백준 1744번 수 묶기

문제 링크 : https://www.acmicpc.net/problem/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보다 작거나 같은 정수이다.

 

출력

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

 

풀이

처음엔 단순히 오름차순 정렬 후 양수는 양수끼리, 음수는 음수끼리 묶어서 더해주면 최대일 줄 알았는데

이 문제 또한 예외 케이스가 존재한다.

1. "1"은 어떤 수와 묶어도 쌉손해다. ex) 1 * 1 -> 1 손해, 1 * 7 -> 1 손해, 1 * 0 -> 1 손해...

2. 수열에 "0"이 존재하는 경우 이득을 볼 수 있다. ex) 0 * -3 -> 3 이득 0 * -1 -> 1 이득 (단, 양수는 x)

이 조건 외에는 처음 생각 그대로 양수, 음수 각각 서로 곱해주면 이득이다.

따라서, 1과 0을 미리 제외한 채(counting은 해줌) 양수, 음수 나눠서 vector에 저장한 후,

0이 있을 때 음수 vector가 홀수이면 가장 높은 음수를 지워버리자!

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int n; scanf("%d", &n);
    vector<int> plus;
    vector<int> minus;
    int zero = 0;
    int one = 0;
    for (int i = 0; i < n; i++) {
        int k; scanf("%d", &k);
        if (k == 1) {
            one++;
        }
        else if (k > 0) {
            plus.push_back(k);
        }
        else if (k < 0) {
            minus.push_back(k);
        }
        else zero++;
    }
    sort(plus.begin(), plus.end(), greater<int>());
    sort(minus.begin(), minus.end());
    if (plus.size() % 2 == 1) plus.push_back(1);
    if (minus.size() % 2 == 1) minus.push_back(zero > 0 ? 0 : 1);
 
    int ans = 0;
    for (int i = 0; i < plus.size(); i += 2) {
        ans += plus[i] * plus[i + 1];
    }
    for (int i = 0; i < minus.size(); i += 2) {
        ans += minus[i] * minus[i + 1];
    }
    ans = ans + one;
    printf("%d", ans);
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~