September 3, 2021

문제

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일방적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

예를 들어, 02948이라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) x 9) x 8) x4) = 576 입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

시간 제한

1초

메모리 제한

128MB

입력 조건

첫째 줄에 여러개의 숫자로 구성된 하나의 문자열 S가 주어진다. ( 1 ≤ S의 길이 ≤ 20)

출력 조건

첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.

풀이

#include <iostream>
#include <string>

using namespace std;

string S;
int maxSum;

void calculateSum() {
    maxSum = S[0] - '0';

    for (int i = 1; i < S.size(); ++i) {
        if (maxSum + (S[i] - '0') > maxSum * (S[i] - '0')) {
            maxSum += S[i] - '0';
        } else {
            maxSum *= S[i] - '0';
        }
    }
}

int main(int argc, char const *argv[]) {
    cin >> S;

    calculateSum();

    cout << maxSum;

    return 0;
}

numberList = map(int, list(input()))
maxSum = 0

for number in numberList:
    if (maxSum * number > maxSum + number):
        maxSum *= number
    else:
        maxSum += number

print(maxSum)

문자열의 모든 숫자를 차례대로 순회하며 각 계산의 결과가 더 큰 연산자를 선택한다.

정당성 분석

각 계산의 결과가 더 작은 연산을 선택할 경우 최종 결과값은 더 작은 결과가 나온다. 즉, 더 결과가 더 작은 연산을 포함하는 최댓값은 없다.