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

문제 링크

1744번: 수 묶기

 

 

풀이 )

  가장 큰 두 수를 뽑아 곱하는 경우가 가장 큰 결과값이 나오기 때문에 먼저 입력받은 수열에 대해서 내림차순으로 정렬해주었다.

 

• 앞에서부터 두 수가 모두 1보다 큰 경우에 대해서 두 수를 곱해준다.
• 한자리씩 검사하여 1이 있는 경우 1은 다른 수와 곱했을 때 합이 최대가 될 수 없으므로 따로 분류해 둔다. (1+n > 1*n)
• 음수 두 수를 곱하면 양수가 되므로 절댓값이 큰 뒤에서 부터 두 수를 곱해준다.
• 음수가 홀수인 경우 마지막으로 남은 수를 처리한다.

위의 4가지를 순서대로 구현했다.

 

#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 idx = 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';
}