[C++] 백준 - 1744 : 수 묶기

문제 링크

1744번: 수 묶기

 

 

풀이 )

  가장 큰 수를 두개 뽑아 곱했을때가 다른 두 수를 곱했을 때보다 결과가 크기 때문에 우선 내림차순으로 정렬했다.

  이후 앞에서부터 두 수를 뽑아 곱한다.

 

  이 때 1과 0은 다른 양수와 곱해지는 경우 곱이 합보다 작아지게 되므로 1부터 예외처리해준다.

  n * 1 < n + 1, n * 0 < n + 0

 

  음수 2개를 곱하는 경우 양수가 되기 때문에 그 값을 최대로 만들기 위해 절댓값이 큰 끝부터 2개씩 곱하면서 더한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];

    sort(v.begin(), v.end(), greater<int>());
    int ans = 0;

    int i = 0;
    for(; i < n; i+=2){
        if(v[i+1] <= 1)
            break;
        ans += v[i]*v[i+1];
    }
    for(; i < n; ++i){
        if(v[i] < 1)
            break;
        ans += v[i];
    }

    int j = n-1;
    for(; j > i; j-=2)
        ans += v[j]*v[j-1];
    if(i == j)
        ans += v[j];

    cout << ans << '\n';
}