[그리디]백준 1744번 수 묶기(C++)

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

 

읽어보면

쉽다

 

 

단순히

오름차순 정렬해주고

 

제일 작은 음수 들끼리 곱해주고, 제일 큰 양수들끼리 곱해주고

 

그 중에서 다 묶고 난 후, 남은 음수가 1개일때, 남은 양수가 1개일때 등

조건만 나눠주면 된다

 

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

    int n;

    cin >> n;

    int arr[n];

    for (int i = 0; i < n; i++)

    {

        cin >> arr[i];

    }

    sort(arr, arr + n);

    int result = 0;

    for (int i = n - 1; i >= 0; i--)

    {

        if (arr[i] >= 0 && arr[i - 1] >= 0)

        {

            if ((arr[i] * arr[i - 1] > arr[i] + arr[i - 1]))

            {

                result += arr[i] * arr[i - 1];

                i--;

            }

            else

                result += arr[i];

        }

        else if (arr[i] >= 0 && (i == 0 || arr[i - 1] < 0))

        {

            result += arr[i];

            break;

        }

    }

    for (int i = 0; i < n; i++)

    {

        if (arr[i] < 0 && arr[i + 1] < 0)

        {

            result += arr[i] * arr[i + 1];

            i++;

        }

        else if (arr[i] < 0 && (arr[i + 1] > 0 || i == n - 1))

        {

            result += arr[i];

            break;

        }

    }

    cout << result;

}

 

오름차순 정렬의 경우

가장 큰 수가 n-1 에 있을 것이다.

 

앞선 양수들끼리 곱하는 경우를 보자

 

당연히 맨 앞에서부터 시작이니까? n-1 ( 가장큰 수의 인덱스 ) 로 부터

차근차근 하나씩 곱하는데

 

두 수의 곱이 더하기보다 작다면 ( 자연수 중에서 이런 경우는 0이 포함된 경우밖에 없음 ) , 따로따로 더해준다.

 

그리고 0보다 큰데, 그 이후의 값이 음수인 경우는 곱해주면 더 큰 음수가 되니까 더해준다

 

음수의 경우는 반대이다