[C++] 백준/Gold/1744. 수 묶기

문제: 수 묶기 (백준 1744번)

문제 분석

주어진 N개의 정수에 대해, 덧셈과 곱셈 연산을 적절히 활용하여 최종 합을 최대화하는 문제이다.

핵심 포인트:

• 양수의 경우 1보다 큰 수들은 곱하는 것이 더 큰 효과를 낼 수 있다.
• 음수와 0의 경우, 두 개씩 묶어 곱하면 음수의 부호를 상쇄하거나 0으로 만들 수 있다.
• 1은 곱셈보다 덧셈하는 것이 유리하다.

문제 해결의 관건은 입력 배열을 정렬한 후, 왼쪽(음수 및 0)과 오른쪽(양수)에서 각각 최적의 조합을 선택하는 것이다.

---

해결 방법

정렬: 배열을 오름차순으로 정렬한다.

양쪽 후보 고려:

• 왼쪽 부분에서는 인접한 두 수의 곱과 개별 값 중 큰 값을 선택한다.
• 오른쪽 부분에서는 인접한 두 수의 곱과 개별 값 중 큰 값을 선택한다.
• 만약 남은 요소가 2개이면, 곱과 덧셈 중 더 큰 값을 선택한다.
• 하나만 남은 경우에는 그대로 더한다.

포인터 이동:

• 후보 값이 왼쪽이나 오른쪽에서 나온 것에 따라 해당 포인터들을 적절히 이동시키며 최종 합(sum)을 갱신한다.

이 방식은 전형적인 “양쪽에서 두 개씩 묶기” 전략과 유사하지만, 여러 후보 연산(단일값, 인접 두 값의 곱, 양쪽 값의 조합 등)을 고려해 그때그때 최적의 선택을 하는 것이 포인트이다.

코드 전체

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    int n; 
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    int left = 0, right = n - 1, sum = 0;
    
    if (n == 1)
    {
        cout << v[0];
        return 0;
    }
    
    while (left <= right)
    {
        vector<int> temp;
        // 후보 값 생성: 남은 구간의 길이가 3 이상이면 여러 후보를 고려
        if (right - left > 1)
            temp.insert(temp.end(), { v[left], v[right], 
                                       v[left] * v[left + 1], 
                                       v[right] * v[right - 1] });
        // 남은 요소가 2개인 경우: 두 가지 경우 비교
        else if (right - left == 1)
            temp.insert(temp.end(), { v[left] * v[right], v[left] + v[right] });
        else
        {
            // 하나만 남으면 그대로 더한다.
            sum += v[left];
            break;
        }
        // 후보 값 중 최댓값 선택
        int maxVal = *max_element(temp.begin(), temp.end());
        
        // 각 후보가 나온 경우에 따라 포인터 조정
        if (maxVal == v[left] && right - left > 1) 
            left++;
        else if (maxVal == v[right] && right - left > 1) 
            right--;
        else if (maxVal == v[right] * v[right - 1]) 
            right -= 2;
        else if (maxVal == v[left] * v[left + 1])
            left += 2;
        else if (maxVal == v[left] * v[right])
            right -= 2;
        else if (maxVal == v[left] + v[right])
            right -= 2;
        
        sum += maxVal;
    }
    cout << sum;
}