C++로 세 정수 표현식의 최댓값 구하기

문제 정의

0이 아닌 세 개의 정수 a, b, c가 주어졌을 때, 이 숫자들 사이에 덧셈(+)과 곱셈(*) 기호를 각각 한 번씩 배치하여 만들 수 있는 식의 최댓값을 구하는 것이 목표입니다.

여기서 중요한 조건은 다음과 같습니다.

숫자의 순서를 자유롭게 재배열할 수 있습니다.
덧셈 기호와 곱셈 기호는 반드시 각각 한 번씩 사용해야 합니다.

예를 들어 a = 1, b = 3, c = 5라면 최댓값은 다음과 같이 20이 됩니다.

(1 + 3) * 5 = 20

접근 방법 및 알고리즘

숫자들의 부호 조합에 따라 최적의 연산 전략이 달라집니다. 네 가지 경우로 나누어 생각할 수 있습니다.

모든 숫자가 양수인 경우: 두 개의 작은 수를 먼저 더한 뒤, 그 결과에 가장 큰 수를 곱하면 최댓값이 됩니다.
양수가 두 개인 경우: 두 양수를 서로 곱하고, 남은 하나의 음수를 더하는 것이 유리합니다.
양수가 하나인 경우: 두 음수를 서로 곱하면 양수가 되므로, 그 곱에 남은 양수를 더하는 것이 최선입니다.
모든 숫자가 음수인 경우: 절댓값이 가장 작은(즉 가장 큰) 두 수를 더한 뒤, 나머지 수와 곱하면 최댓값을 얻을 수 있습니다.

C++ 구현 예제

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

int getMaximumResult(int a, int b, int c){
    int negativeCnt = 0;
    int sum = a + b + c;
    int mul = a * b * c;
    int largest = max(a, max(b, c));
    int smallest = min(a, min(b, c));
    if (a < 0) {
        ++negativeCnt;
    }
    if (b < 0) {
        ++negativeCnt;
    }
    if (c < 0) {
        ++negativeCnt;
    }
    if (negativeCnt == 0) {
        // 모두 양수: 작은 두 수의 합 × 가장 큰 수
        return (sum - largest) * largest;
    }
    else if (negativeCnt == 1) {
        // 음수가 하나: 두 양수의 곱 + 음수
        return (mul / smallest) + smallest;
    }
    else if (negativeCnt == 2) {
        // 음수가 둘: 두 음수의 곱 + 양수
        return (mul / largest) + largest;
    }
    else if (negativeCnt == 3) {
        // 모두 음수: 큰 두 수의 합 × 가장 작은 수
        return (sum - smallest) * smallest;
    }
}

int main(){
    int a = 1, b = 3, c = 5;
    cout << "Maximum value = " << getMaximumResult(a, b, c) << endl;
    return 0;
}

코드 설명

위 코드는 다음과 같은 흐름으로 동작합니다.

세 수의 총합(sum)과 전체 곱(mul), 그리고 최댓값과 최솟값을 미리 계산해 둡니다.
음수의 개수(negativeCnt)를 세어 네 가지 경우를 구분합니다.
(sum - largest)는 '가장 큰 수를 제외한 두 수의 합', (mul / smallest)은 '가장 작은 수를 제외한 두 수의 곱'을 의미하므로, 나눗셈과 뺄셈만으로 각 경우의 최적 식을 손쉽게 계산할 수 있습니다.

시간 복잡도는 상수 개수의 비교와 산술 연산만 수행하므로 O(1)입니다.

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 출력이 생성됩니다.

Maximum value = 20