[백준] 1744 수 묶기

문제 주소 : www.acmicpc.net/problem/1744

1744번: 수 묶기

문제 확인

 

특별한 알고리즘이 필요한 문제는 아닙니다.

곱셈의 특성을 이용하여 풀면 쉽게 풀 수 있습니다.

문제에서 고려해야 할 점은 3가지입니다.

1. 곱셈은 큰 수 끼리 곱할수록 더욱 커집니다.
2. 두 음수의 곱은 양수입니다.
3. A X 1 = A 입니다. => A + 1 이 A X 1 보다 크므로 이 수는 묶지 않습니다.

 

풀이

 

1, 2번 특성을 이용하기 위해서는 수열이 정렬되어 있어야 합니다. 간단하게 std::sort를 이용하여 정렬을 해 줍니다.

정렬이 끝나면 0번째부터 음수끼리 묶어 양수를 만들어 내 더합니다. 이때 음수 또한 1번 특성을 고려하여 (0,1), (2,3)으로 차례대로 묶어가면 더욱 큰 수를 얻을 수 있습니다. 음수 계산 시 0을 포함하여 계산을 하여 홀로 남은 음수를 0과 곱하여 0으로 만들어 줍니다. 이 과정을 양수가 나올 때까지 반복합니다.

양수의 경우 1번 특성을 이용하기 위하여 n-1번째 부터 역순으로 묶습니다. 주의해야 할 점은 3번 특성을 고려하여 2 이상의 양수만 묶습니다.

위 과정이 끝나면 남은 수 들을 더합니다.

 

코드

#include <cstdio>
#include <algorithm>
int main() {
    int n, ary[10000], ans=0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &ary[i]);
    std::sort(ary, ary + n);//정렬
    int i = 0, j = n-1;
    while (i + 1 < n &&ary[i] <= 0 && ary[i + 1] <= 0) {//음수를 양수가 나올 때 까지 묶기
        ans += ary[i] * ary[i + 1];
        i += 2;
    }
    while (j > 0 &&ary[j] > 1 && ary[j - 1] > 1) {//2 이상의 양수 묶기
        ans += ary[j] * ary[j - 1];
        j -= 2;
    }
    while (i <= j) //남은 수들을 더함
        ans += ary[i++];
    printf("%d", n > 1 ? ans : ary[0]);
}