[백준 1744번] 수 묶기

문제 링크: 1744번 제목

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

 

다행히 생각보다는 분기를 많이하지 않았지만 그렇다고 해서 복잡하지 않은 문제는 아닙니다. 저는 수열을 정렬한 후, 먼저 양수 부분수열을 처리하고, 0 또는 음수인 부분수열을 처리하는 방식으로 진행했습니다. 코드에서와 마찬가지로, 여기서도 편의상 내림차순으로 정렬하겠습니다.

 

7   4   3   3   2   1   0   -2   -2   -3   -4   -5   -5   -6

 

위에서 양수 부분수열은 하늘색 부분입니다. 그리디하게 큰 수끼리 곱해서, 즉 앞에서부터 두 개씩 곱해서 더해줍니다. 그 후, 주황색 부분수열도 절댓값이 큰 수부터, 즉 뒤에서부터 두 개씩 곱해서 더해줍니다. 여기서 0은 음수와 구분할 필요가 없는데, 0이라고 하더라도 어차피 음수와 곱해서 0으로 만들어주는 편이 각각을 따로 더하는 것보다 이득이기 때문입니다.

 

다만 여기서 주의할 것은, 하늘색 부분에서의 2, 1입니다. 1을 곱한 것보다는 각각을 따로 더하는 것이 이득이기 때문에, 반드시 예외 처리를 해야 합니다.

 

#include <stdio.h>
#include <stdlib.h>

int n;
int t[50];

int comp(const void *a, const void *b);

int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &(t[i]));
    }
    qsort(t, n, sizeof(int), comp);

    int l = -1;
    for (int i = 0; i < n; i++) {
        if (t[i] > 0) {
            l = i;
        }
    }

    int ans = 0;
    int idx;

    if (l >= 0) {
        idx = 0;
        while (idx + 1 <= l) {
            if (t[idx] * t[idx + 1] >= t[idx] + t[idx + 1]) {
                ans += t[idx] * t[idx + 1];
            } else {
                ans += t[idx] + t[idx + 1];
            }
            idx += 2;
        }
        if (idx == l) {
            ans += t[idx];
        }
    }

    idx = n - 1;
    while (idx - 1 > l) {
        ans += t[idx] * t[idx - 1];
        idx -= 2;
    }
    if (idx == l + 1) {
        ans += t[idx];
    }

    printf("%d", ans);
}

int comp(const void *a, const void *b) {
    int n1 = *(int *)a;
    int n2 = *(int *)b;
    return (int)n2 - (int)n1;
}