[C++] BOJ(백준) 1744 수 묶기

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

1744번: 수 묶기

 

그리디 문제다.

 

수의 곱과 합으로 최대값을 찾는 문제이므로 정렬을 먼저 했다.

처음에는 정렬 후 큰 수부터 곱과 합의 크기를 비교하고 큰 쪽으로 결과 값에 더해주는 방식으로 했다.

이 때 곱이 크면 인덱스를 하나 더 줄여주고, 합이 크면 현재 인덱스의 값만 더한다.

(쓰다보니 필요 없는 부분인가 싶다)

 

간과한 점은 음수도 들어올 수 있다는 점이다.

음수의 경우 작은 음수끼리 곱할 수록 값이 커진다.

따라서 위의 과정에서 음수와의 계산을 해야할 경우 반복문을 멈추고

작은 음수부터 같은 과정을 반복한다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int arr[50];

int main() {
    // 입출력 속도를 단축시키기 위함
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, i, j;  cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);

    int re = 0;
    // 양수
    for (i = n - 1; i > 0; i--) {
        if (arr[i - 1] < 0) break;
        // 수 묶기 여부
        if (arr[i] * arr[i - 1] > arr[i] + arr[i - 1]) {
            re += arr[i] * arr[i - 1];
            i--;
        }
        else re += arr[i];
    }

    // 음수
    for (j = 0; j < i; j++) {
        // 수 묶기 여부
        if (arr[j] * arr[j + 1] > arr[j] + arr[j + 1]) {
            re += arr[j] * arr[j + 1];
            j++;
        }
        else re += arr[j];
    }

    if (j == i) re += arr[j];
    cout << re;
}