백준 1744: 수 묶기

문제 요약

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

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

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

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

문제 분류

• 그리디 알고리즘
• 정렬
• 많은 조건 분기

문제 풀이

계속해서 가장 큰 수끼리 묶으면 되는 그리디 알고리즘이다.
기본적인 아이디어는, 주어진 수의 순서는 중요하지 않으므로 우선 내림차순으로 정렬하고,0부터 n까지 i로 탐색하며 ary[i]와 ary[i + 1]에 따라 필요한 연산을 실행하면 된다.

우선 두 수가 양수라면 무조건 곱하는 것이 더 클 것이다. 다만 예외가 있는데, 두 수 중에 한 수라도 1인 경우에는 더하는 것이 더 크다.

두 수가 음수라도 무조건 곱해야 한다. 두 음수를 곱하면 양수가 되기 때문에, 가장 절대값이 큰 두 음수부터 곱해서 더해야 한다.

이 때, 음수의 개수가 홀수라면 어떻게 될까? 내림차순 정렬이므로 절대값이 작은 음수부터 탐색하게 되는데, 무조건 절대값이 가장 큰 음수부터 쌍으로 짝지어 곱해야한다. 즉, 절대값이 가장 작은 음수는 그냥 더해야 한다. 이를 위해 음수의 홀수 여부를 isMinus로 저장하였다. 즉, ary[i]가 음수이며,isMinus가 true인 경우 해당 값을 더하고, isMinus를 false로 바꾼다.

마지막으로 ary[i]가 0인 경우이다. 0은 그냥 더하는 것 외에 하나의 음수를 곱하여 없앨 수 있다. isMinus가 true인 경우 0과 곱하는 것으로 isMinus를 false로 바꾸며, 음수 하나를 건너뛰어야 한다는 의미의 flag변수를 둔다. flag이면 0을 통해 하나의 음수를 0으로 쳐서 합하지 않아도 되므로 flag를 false로, isMinus역시 false로 바꾸며, 딱히 다른 연산은 하지 않는다.

많은 경우와 조건들을 파악한다면 어렵지 않다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, ary[50], res = 0;
    bool isMinus = false, flag = false;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", ary + i);
        if (ary[i] < 0) isMinus = !isMinus;
    }
    sort(ary, ary + n, greater<>());
    for (int i = 0; i < n; i++) {
        if (ary[i] > 1) {
            if (i + 1 < n && ary[i + 1] > 1) {
                res += ary[i] * ary[i + 1];
                i++;
            }
            else
                res += ary[i];
        }
        else if (ary[i] == 1) res += ary[i];
        else if (ary[i] == 0) {
            if (isMinus) flag = true;
        }
        else {
            if (flag) {
                flag = false;
                isMinus = false;
            }
            else {
                if (isMinus) {
                    res += ary[i];
                    isMinus = false;
                }
                else {
                    res += ary[i] * ary[i + 1];
                    i++;
                }
            }
        }
    }
    printf("%d", res);

    return 0;
}