[C/C++] 백준 #1744 수 묶기(탐욕 알고리즘)

이 문제는 탐욕 알고리즘으로 풀기에 괜찮은 문제입니다.

 

 

수열이 주어지면 그 수를 다른 수와 묶어서 곱한 후 더하거나 수 자체를 더하는 방법을 사용합니다.  한번 사용된 수는 다시 사용될 수 없습니다.  그리고 모든 수가 참여되어야 합니다.  이렇게 했을 때 최대의 합을 구하는 것이 문제입니다.

 

예를 들어서 ( 3, -2, 5, -7, 0 ) 이 있다고 한다면,   (-2 * -7) + (3 * 5) + 0을 하면 가장 최대수를 얻게 됩니다.

 

원리는 간단합니다.  0 이하의 수와 1보다 큰 수들, 그리고 1의 갯수를 구합니다.  \(1a = a\)이므로 1은 곱하기보다는 자기 자신으로 더하는 것이 더 큰 수가 됩니다.

 

( 2, 3, 5, 7 ) 이렇게 4개의 수가 있다면, 가장 큰 값을 얻기 위해서는 큰수끼리 곱해나가는 것이 좋습니다.  (5*7) + (2*3)이 가장 큰 수가 되는 것이죠.

 

그래서 0이하의 수는 작은수부터 큰 수 순으로 합니다.  그러면 절대값이 큰 것이 왼쪽에 모입니다.  1 초과 수는 큰수에서 작은수 순으로 합니다.  그러면 역시 절대값이 큰 것이 왼쪽에 모입니다.  그러면 차례대로 2개씩 묶어 나가면 됩니다.  0 이하의 수가 홀수개이면 어쩔 수 없이 마지막 수는 더해줍니다.  모든 수가 침여해야 하기 때문이죠.  1 초과 수도 마찬가지입니다.  홀수개가 있으면 마지막 남은 수는 더해줍니다.

 

정렬알고리즘을 사용하기 때문에 알고리즘 효율은 \(O(n \log n)\)이 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------
//    baekjoon #1744
//        - by Aubrey Choi
//        - created at 2019-11-13
//----------------------------------------------------
#include <stdio.h>
#include <algorithm>

bool cmp(int a, int b) { return a>b; }
int main()
{
    int n, v1[10000], v2[10000], s, n1=0, n2=0, ans=0;
    scanf("%d",&n);
    while(n--) { scanf("%d",&s); if(s<=0) v1[n1++]=s; else if(s==1) ans++; else v2[n2++]=s; }
    std::sort(v1, v1+n1); std::sort(v2,v2+n2,cmp);
    for(int i=0;i<n1-1;i+=2) ans+=v1[i]*v1[i+1];
    if(n1&1) ans+=v1[n1-1];
    for(int i=0;i<n2-1;i+=2) ans+=v2[i]*v2[i+1];
    if(n2&1) ans+=v2[n2-1];
    printf("%d\n", ans);
}